QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#267026#7869. 建设终末树zyz070 2129ms698440kbC++176.5kb2023-11-26 21:27:172023-11-26 21:27:18

Judging History

你现在查看的是最新测评结果

  • [2023-11-26 21:27:18]
  • 评测
  • 测评结果:0
  • 用时:2129ms
  • 内存:698440kb
  • [2023-11-26 21:27:17]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(auto Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(auto Ti=(Ta);Ti>=(Tb);--Ti)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
using ll=long long;
const int N=2005,V=N*N*4;
int n,m,q,tag[N],cnt[N],fa[N],fai[N];
vector<pair<int,int>> e[N];
vector<int> A[N];
void get_fa(int u){
	for(auto [v,i]:e[u]){
		if(v!=fa[u]){
			fa[v]=u;
			fai[v]=i;
			get_fa(v);
		}
	}
}
int siz[N],dep[N],hson[N];
void dfs1(int u){
	siz[u]=1;
	dep[u]=dep[fa[u]]+1;
	for(auto [v,i]:e[u]){
		if(v!=fa[u]){
			dfs1(v);
			siz[u]+=siz[v];
			if(siz[v]>siz[hson[u]]){
				hson[u]=v;
			}
		}
	}
}
int dfn[N],rk[N],dfx,top[N];
void dfs2(int u,int tp){
	rk[dfn[u]=++dfx]=u;
	top[u]=tp;
	if(hson[u]){
		dfs2(hson[u],tp);
	}
	for(auto [v,i]:e[u]){
		if(v!=fa[u]&&v!=hson[u]){
			dfs2(v,v);
		}
	}
}
// 0 -> up, 1 -> down
// i: edge, j: item
int id(int i,int j,bool one){
	return (j-1)*(n-1)+i+one*m*(n-1);
}
int tot;
template<int N>
struct DSU{
	int n,fa[N];
	void init(int _n){
		n=_n;
		For(i,1,n) fa[i]=i;
	}
	int find(int u){
		for(;u!=fa[u];u=fa[u]=fa[fa[u]]);
		return u;
	}
	bool merge(int u,int v){
		u=find(u);
		v=find(v);
		fa[u]=v;
		return u!=v;
	}
};
DSU<N*N> dsu;
struct Edge{
	int v,nxt;
}edg[int(3e7)];
int bel[V],head[V],ecnt;
void add_edge(int u,int v){
	u=bel[u];
	v=bel[v];
	edg[++ecnt]={v,head[u]};
	head[u]=ecnt;
}
void dfs(int u,int i,int len){
	cnt[u]=(tag[u]==i);
	for(auto [v,_]:e[u]){
		if(v!=fa[u]){
			dfs(v,i,len);
			cnt[u]+=cnt[v];
		}
	}
	if(u>1){
		if(!cnt[u]){
			add_edge(id(fai[u],i,1),id(fai[u],i,0));
		}else if(cnt[u]==len){
			add_edge(id(fai[u],i,0),id(fai[u],i,1));
		}
	}
}
struct Two_Sat{
	struct Vert{
		int dfn,low,bel;
		bool in;
	}t[V];
	int dfx,scc_cnt,stk[V],top;
	void tarjan(int u){
		t[u].dfn=t[u].low=++dfx;
		stk[++top]=u;
		t[u].in=1;
		for(int i=head[u];i;i=edg[i].nxt){
			int v=edg[i].v;
			if(!t[v].dfn){
				tarjan(v);
				t[u].low=min(t[u].low,t[v].low);
			}else if(t[v].in){
				t[u].low=min(t[u].low,t[v].dfn);
			}
		}
		if(t[u].low==t[u].dfn){
			++scc_cnt;
			while(1){
				int v=stk[top--];
				t[v].bel=scc_cnt;
				t[v].in=0;
				if(v==u) break;
			}
		}
	}
	void solve(){
		For(i,1,tot){
			if(!t[i].dfn){
				tarjan(i);
			}
		}
	}
}sat;
int color(int u){
	return sat.t[bel[u]].bel;
}
struct Rollback_DSU{
	int fa[N],siz[N];
	vector<int> op;
	int find(int u){
		return u==fa[u]?u:find(fa[u]);
	}
	void init(){
		For(i,1,m){
			fa[i]=i;
			siz[i]=1;
		}
	}
	void merge(int u,int v){
		u=find(u);
		v=find(v);
		if(u!=v){
			if(siz[u]<siz[v]){
				swap(u,v);
			}
			fa[v]=u;
			siz[u]+=siz[v];
			op.push_back(v);
		}
	}
	void undo(unsigned ver){
		while(op.size()>ver){
			int v=op.back();
			op.pop_back();
			siz[fa[v]]-=siz[v];
			fa[v]=v;
		}
	}
}dsu2;
struct Segment_Tree{
	vector<pair<int,int>> ins[N*4];
	DSU<N> dsu[N*4];
	void init(int p=1,int L=2,int R=n){
		dsu[p].init(m);
		if(L==R) return;
		int mid=(L+R)/2;
		init(p*2,L,mid);
		init(p*2+1,mid+1,R);
	}
	void range_link(int l,int r,int u,int v,int p=1,int L=2,int R=n){
		if(l<=L&&R<=r){
			if(dsu[p].merge(u,v)){
				ins[p].emplace_back(dsu[p].find(u),dsu[p].find(v));
			}
			return;
		}
		int mid=(L+R)/2;
		if(l<=mid) range_link(l,r,u,v,p*2,L,mid);
		if(r>mid) range_link(l,r,u,v,p*2+1,mid+1,R);
	}
	void iterate(int p=1,int L=2,int R=n){
		auto ver=dsu2.op.size();
		for(auto [u,v]:ins[p]){
			dsu2.merge(u,v);
		}
		if(L==R){
			if(L>1){
				int i=fai[rk[L]];
				For(j,1,m){
					int k=dsu2.find(j);
					if(j!=k){
						::dsu.merge(id(i,k,0),id(i,j,0));
					}
				}
			}
			dsu2.undo(ver);
			return;
		}
		int mid=(L+R)/2;
		iterate(p*2,L,mid);
		iterate(p*2+1,mid+1,R);
		dsu2.undo(ver);
	}
}seg;
int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	// assert(freopen("B.in","r",stdin));
	// assert(freopen("B.out","w",stdout));
	cin>>n>>m>>q;
	For(i,1,n-1){
		int u,v;
		cin>>u>>v;
		e[u].emplace_back(v,i);
		e[v].emplace_back(u,i);
	}
	get_fa(1);
	dfs1(1);
	dfs2(1,1);
	tot=m*(n-1)*2;
	For(i,1,m){
		int len;
		cin>>len;
		A[i].resize(len);
		For(j,0,len-1) cin>>A[i][j];
	}
	dsu.init(m*(n-1));
	seg.init();
	For(_,1,q){
		vector<int> V,S;
		int lV,lS;
		cin>>lV;
		V.resize(lV);
		For(i,0,lV-1) cin>>V[i];
		cin>>lS;
		S.resize(lS);
		For(i,0,lS-1) cin>>S[i];
		sort(range(V),[](int u,int v){
			return dfn[u]<dfn[v];
		});
		auto merge=[&](int u,int v,int i,int j){
			while(top[u]!=top[v]){
				if(dep[top[u]]<dep[top[v]]){
					swap(u,v);
				}
				seg.range_link(dfn[top[u]],dfn[u],i,j);
				u=fa[top[u]];
			}
			if(u!=v){
				if(dfn[u]<dfn[v]){
					swap(u,v);
				}
				seg.range_link(dfn[v]+1,dfn[u],i,j);
			}
		};
		For(i,0,lS-2){
			For(j,0,lV-1){
				merge(V[j],V[(j+1)%lV],S[i],S[i+1]);
			}
		}
	}
	dsu2.init();
	seg.iterate();
	{
		int x=m*(n-1);
		For(i,1,x){
			bel[i]=dsu.find(i);
		}
		For(i,x+1,x*2){
			bel[i]=bel[i-x]+x;
		}
		For(i,x*2+1,x*4){
			bel[i]=i;
		}
	}
	debug("%d\n",int(clock()));
	For(i,1,m){
		for(int u:A[i]){
			tag[u]=i;
		}
		dfs(1,i,A[i].size());
		vector<int> pre(n+1),suf(n+1);
		For(u,1,n){
			int cur=0;
			for(auto [v,j]:e[u]){
				if(v!=fa[u]){
					pre[v]=cur;
					if(cur){
						++tot;
						add_edge(tot,cur);
						add_edge(tot,id(j,i,0));
						cur=tot;
					}else{
						cur=id(j,i,0);
					}
				}
			}
			reverse(range(e[u]));
			cur=0;
			for(auto [v,j]:e[u]){
				if(v!=fa[u]){
					suf[v]=cur;
					if(cur){
						++tot;
						add_edge(tot,cur);
						add_edge(tot,id(j,i,0));
						cur=tot;
					}else{
						cur=id(j,i,0);
					}
				}
			}
			reverse(range(e[u]));
			for(auto [v,j]:e[u]){
				if(v!=fa[u]){
					if(u>1){
						add_edge(id(j,i,1),id(fai[u],i,1));
					}
					if(pre[v]){
						add_edge(id(j,i,1),pre[v]);
					}
					if(suf[v]){
						add_edge(id(j,i,1),suf[v]);
					}
				}else if(cur){
					add_edge(id(j,i,0),cur);
				}
			}
		}
	}
	debug("tot=%d,ecnt=%d\n",tot,ecnt);
	debug("%d\n",int(clock()));
	sat.solve();
	debug("%d\n",int(clock()));
	For(i,1,n-1){
		For(j,1,m){
			if(color(id(i,j,0))==color(id(i,j,1))){
				cout<<"-1\n";
				return 0;
			}
		}
	}
	For(j,1,m){
		For(u,1,n){
			bool flg=1;
			for(auto [v,i]:e[u]){
				flg&=(color(id(i,j,1))<color(id(i,j,0)))==(v==fa[u]);
			}
			if(flg){
				cout<<u<<' ';
				break;
			}
		}
	}
	cout<<'\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 2129ms
memory: 698440kb

input:

1999 1998 27199
1368 233
233 617
233 388
233 1127
1905 233
907 233
233 40
233 1325
233 1940
1739 233
501 233
233 33
735 233
233 283
233 1427
1992 233
233 632
233 685
1188 233
648 233
233 344
233 1321
986 233
848 233
770 233
256 233
164 233
936 233
1206 233
53 233
1054 233
1430 233
1714 233
86 233
11...

output:

1 1 1 233 1 233 233 1 1 233 233 1 233 1 233 233 233 233 1 233 233 233 233 1 233 1 1 1 1 233 1 233 233 233 233 1 1 233 233 233 1 233 233 1 233 1 233 1 1 899 1 1 233 233 233 1 233 233 233 233 1 233 1 1 233 233 233 1 1 233 233 1 233 233 233 233 1 1 1 233 233 233 233 1 1 1 1 233 233 233 233 233 1 233 23...

result:

wrong answer restrict 3 is not satisfied.

Subtask #2:

score: 0
Wrong Answer

Test #8:

score: 0
Wrong Answer
time: 2ms
memory: 12504kb

input:

10 10 8
4 2
2 9
6 9
8 7
4 10
7 2
5 2
2 1
5 3
3 10 7 2
2 10 2
2 4 10
2 10 4
2 8 2
2 4 10
1 8
2 2 10
1 1
1 10
2 10 9
3 10 3 4
2 7 1
3 10 6 3
2 4 8
2 3 2
4 2 9 4 6
2 5 7
2 3 9
2 2 1
4 10 6 8 5
4 10 6 1 2
2 1 4
2 7 5
2 5 3
2 8 3

output:

2 2 4 4 2 4 8 2 1 10 

result:

wrong answer restrict 1 is not satisfied.

Subtask #3:

score: 0
Wrong Answer

Test #19:

score: 0
Wrong Answer
time: 25ms
memory: 42336kb

input:

500 498 5000
60 409
462 125
461 410
42 178
133 372
137 265
358 27
450 294
45 454
76 405
132 118
333 331
365 230
114 218
112 377
49 429
60 299
488 95
85 362
89 33
426 308
427 198
468 481
289 363
195 430
61 21
162 55
12 487
395 85
79 475
391 215
244 351
331 43
452 186
247 271
224 390
206 347
447 165
9...

output:

498 263 387 434 163 4 212 216 174 274 398 168 385 326 1 454 302 1 453 1 477 149 52 361 44 36 104 75 25 278 353 280 447 1 74 31 287 1 89 270 304 1 224 421 109 429 346 495 193 381 406 119 206 174 1 219 452 488 305 371 83 213 311 42 1 276 387 1 5 282 498 29 471 472 251 120 1 70 1 1 431 322 37 241 404 3...

result:

wrong answer restrict 1 is not satisfied.

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #3:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%