如题所述

这份代码本机上跑几组样例都对了

但是CF上TLE了……

#include <iostream>
const int N = 5005;
struct EDGE {
	int t, next;
	EDGE (const int& _t = 0,const int& _n = 0) 
	: t(_t), next(_n) {}
} edge[N<<1];
int head[N<<1], edge_tot = 1;
void add_edge(int f,int t) {
	edge[head[f] = ++edge_tot] = EDGE(t,head[f]);
}
int ans[N], id[N];
int ptt[N], blg[N];
bool baned[N];
int stamp[N], refer[N];
int n, m, d;
bool match(int u,int time) {
	for(int i = head[u], v;i;i = edge[i].next) {
		if(baned[i>>1]) 
			continue;
		v = edge[i].t;
		if(stamp[v] == time) 
			continue;
		stamp[v] = time;
		if(!refer[v]||match(refer[v],time)) {
			refer[v] = u;
			return true;
		}
	}
	return false;
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;++i) 
		scanf("%d",&ptt[i]);
	for(int i = 1;i <= n;++i) 
		scanf("%d",&blg[i]);
	for(int i = 1;i <= n;++i) {
		add_edge(ptt[i],blg[i]+N);
		add_edge(blg[i]+N,ptt[i]);
	}
	scanf("%d",&d);
	for(int i = 1;i <= d;++i) {
		scanf("%d",&id[i]);
		baned[id[i]] = true;
	}
	int time_cnt = 1;
	for(int i = d;i >= 1;--i, ++time_cnt) {
		for(ans[i] = ans[i+1];match(ans[i],time_cnt);++ans[i], ++time_cnt);
		baned[id[i]] = false;
	}
	for(int i = 1;i <= d;++i) 
		printf("%d\n",ans[i]);
	return 0;
}