提交记录

蒟蒻认为只有建边有问题，其他地方经测试均无误，暴力建边可拿80+

每个部分的建边方式如上

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;

int n,m,k,a[N];
int head[N<<2],tot;
struct sd{
	int to,next;
}edge[N*40];
inline void add(int x,int y){
	edge[++tot].to=y;
	edge[tot].next=head[x];
	head[x]=tot;
	return;
}
int dfn[N<<2],low[N<<2],cnt,scc[N<<2],scc_cnt;
int p1[N],p0[N],pre1[N],pre0[N];
stack<int> st,sim;
inline void tarjan(int sta){
	sim.push(sta),st.push(sta);
	dfn[sta]=low[sta]=++cnt;
	while(!sim.empty()){
		int x=sim.top();
		for(int i=head[x];i;i=edge[i].next){
			int y=edge[i].to;
			if(!dfn[y]){
				dfn[y]=low[y]=++cnt;
				sim.push(y),st.push(y);
				break;
			}
		}
		if(x==sim.top()){
			for(int i=head[x];i;i=edge[i].next){
				int y=edge[i].to;
				if(!scc[y]) low[x]=min(low[y],low[x]); 
			}
			if(dfn[x]==low[x]){
				scc[x]=++scc_cnt;
				while(st.top()!=x){
					scc[st.top()]=scc_cnt;
					st.pop();
				}
				st.pop();
			}
			sim.pop();
		}
	}	
	return;
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++) p0[i]=i,p1[i]=i+n,pre0[i]=i+2*n,pre1[i]=i+3*n;
	for(int x,y,i=1;i<=m;i++) scanf("%d%d",&x,&y),add(p0[x],p1[y]),add(p0[y],p1[x]);
	int siz;
	while(k--){
		scanf("%d",&siz);
		for(int i=1;i<=siz;i++) scanf("%d",a+i);
//		for(int i=1;i<=siz;i++)
//			for(int j=1;j<=siz;j++)
//				if(i!=j) add(p1[a[i]],p0[a[j]]); 
//		a[siz+1]=a[1],a[0]=a[siz];
		for(int i=1;i<=siz;i++){
			if(i==1) add(p1[a[i]],pre0[a[i+1]]);
			else if(i==siz) add(p1[a[i]],pre1[a[i-1]]);
			else add(p1[a[i]],pre0[a[i+1]]),add(p1[a[i]],pre1[a[i-1]]);
		}
		for(int i=1;i<siz;i++)
			add(pre0[a[i]],pre0[a[i+1]]),add(pre0[a[i]],p0[a[i]]);
		add(pre0[a[siz]],p0[a[siz]]);
		for(int i=2;i<=siz;i++)
			add(pre1[a[i]],pre1[a[i-1]]),add(pre1[a[i]],p0[a[i]]);
		add(pre1[a[1]],p0[a[1]]);
	}
	for(int i=1;i<=(n<<2);i++) if(!dfn[i]) tarjan(i);
//	for(int i=1;i<=(n<<1);i++)	printf("i=%d\n",scc[i]); 	
	for(int i=1;i<=(n<<1);i++) if(scc[i]==scc[i+n]) {printf("NIE");return 0;}
	printf("TAK");
	return 0;
}