QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#267060#7869. 建设终末树zyz0710 2146ms657804kbC++177.2kb2023-11-26 21:52:362023-11-26 21:52:36

Judging History

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

  • [2023-11-26 21:52:36]
  • 评测
  • 测评结果:10
  • 用时:2146ms
  • 内存:657804kb
  • [2023-11-26 21:52:36]
  • 提交

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);
		}
	}
}
int mn[N][12];
int argmin(int u,int v){
	return dfn[u]<dfn[v]?u:v;
}
void build(){
	dep[0]=-1;
	For(i,1,n) mn[i][0]=fa[rk[i]];
	For(j,1,11){
		For(i,1,n-(1<<j)+1){
			mn[i][j]=argmin(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
		}
	}
}
int lca(int u,int v){
	if(u==v) return u;
	if((u=dfn[u])>(v=dfn[v])) swap(u,v);
	int k=__lg(v-(u++));
	return argmin(mn[u][k],mn[v-(1<<k)+1][k]);
}
// 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,typename T=short>
struct DSU{
	T 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;
	}
	void merge(int u,int v){
		fa[find(u)]=find(v);
	}
};
DSU<N*N,int> 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{
	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){
			dsu[p].merge(u,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(i,1,m){
			dsu2.merge(dsu[p].fa[i],i);
		}
		if(L==R){
			if(L>1){
				int i=fai[rk[L]];
				For(j,1,m){
					::dsu.merge(id(i,dsu2.fa[j],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);
	#ifdef LOCAL
	assert(freopen("B.in","r",stdin));
	assert(freopen("B.out","w",stdout));
	#endif
	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);
	build();
	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];
		});
		vector<pair<int,int>> chains;
		static int stk[N];
		int len=0;
		stk[len=1]=1;
		for(int u:V){
			int lca=::lca(u,stk[len]);
			if(lca!=stk[len]){
				while(len>1&&dfn[stk[len-1]]>dfn[lca]){
					chains.emplace_back(stk[len-1],stk[len]);
					--len;
				}
				chains.emplace_back(lca,stk[len]);
				if(stk[len-1]!=lca) stk[len]=lca;
				else --len;
			}
			stk[++len]=u;
		}
		For(i,1,len-1){
			chains.emplace_back(stk[i],stk[i+1]);
		}
		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(auto [u,v]:chains){
				merge(u,v,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: 10
Accepted

Test #1:

score: 10
Accepted
time: 1833ms
memory: 638436kb

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:

1294 1264 1662 1036 1036 1450 899 641 906 1005 1005 1683 1547 1547 878 1654 1630 1085 503 1338 1654 641 1388 1388 878 1904 1547 1036 1662 1388 906 906 1662 987 878 1683 467 815 1662 1909 1388 1654 899 9 1338 1450 1909 1610 1671 899 1671 181 1036 906 987 467 899 815 705 705 641 1547 899 1904 1662 154...

result:

ok Accepted.

Test #2:

score: 0
Accepted
time: 1894ms
memory: 640496kb

input:

1998 2000 25224
1860 579
579 1400
720 579
579 1379
579 1628
579 69
579 400
1941 579
579 811
579 252
1816 579
579 1786
579 335
579 1467
1480 579
98 579
579 755
579 55
579 1059
650 579
579 1846
1437 579
579 861
338 579
1687 579
579 1248
579 1827
579 1169
1613 579
579 1494
579 1502
1090 579
612 579
579...

output:

219 942 158 865 295 1458 219 158 1855 906 557 295 1855 1545 422 557 1545 937 1855 906 634 872 872 1442 1458 1450 158 239 872 295 422 942 295 937 1689 1213 295 634 219 1183 1855 1213 443 1450 1458 872 1117 488 239 1577 698 865 422 219 1699 443 1823 1183 1689 634 488 1117 1545 323 1458 323 1458 443 90...

result:

ok Accepted.

Test #3:

score: 0
Accepted
time: 2140ms
memory: 640428kb

input:

1999 1999 17845
621 466
466 254
1001 466
466 326
466 779
466 40
527 466
466 1130
466 504
466 1136
466 73
466 1156
963 466
466 1095
247 466
466 1146
1361 466
466 1340
774 466
466 422
466 1649
466 948
466 1803
466 1765
686 466
466 551
612 466
608 466
318 466
466 132
1215 466
466 310
1962 466
466 1999
...

output:

1046 842 80 647 1792 1241 1483 904 981 1483 1046 1732 904 80 647 544 1085 904 1399 1345 1792 647 904 647 1483 1345 594 1732 380 544 1792 1471 1792 586 1046 1120 544 1478 1399 1792 1732 380 1345 1190 1824 1046 594 647 647 904 1792 1732 380 1732 1478 1085 1120 1860 586 1013 1824 1471 981 1995 1190 147...

result:

ok Accepted.

Test #4:

score: 0
Accepted
time: 1832ms
memory: 638424kb

input:

1999 1999 23606
1568 1784
784 1568
1253 1568
1568 869
1568 1404
1601 1568
262 1568
1661 1568
1568 335
1839 1568
1568 208
1154 1568
1568 400
1576 1568
1112 1568
187 1568
1568 1370
1568 1451
1568 293
1568 344
1037 1568
13 1568
1568 1240
518 1568
1568 1912
1121 1568
1005 1568
1568 887
1510 1568
1568 71...

output:

-1

result:

ok Accepted.

Test #5:

score: 0
Accepted
time: 2146ms
memory: 640176kb

input:

1998 1998 17047
512 545
545 1651
497 545
545 1154
545 1847
545 1201
898 545
1304 545
545 915
495 545
545 71
1361 545
545 1508
1070 545
545 221
545 593
1612 545
545 1011
545 13
913 545
1659 545
545 1557
545 1425
545 1065
1673 545
545 170
1602 545
680 545
982 545
1600 545
545 1784
678 545
1484 545
191...

output:

-1

result:

ok Accepted.

Test #6:

score: 0
Accepted
time: 1692ms
memory: 640660kb

input:

2000 1999 30204
1179 128
586 1179
1179 1556
1179 330
1412 1179
83 1179
147 1179
636 1179
1179 1584
1429 1179
212 1179
1179 1724
19 1179
1179 160
1179 1326
964 1179
1179 624
1179 1498
1137 1179
442 1179
1179 1027
1179 309
1179 1767
1179 721
198 1179
899 1179
211 1179
1179 1740
1746 1179
1179 828
568 ...

output:

1987 49 881 880 1837 47 627 89 49 1159 1896 49 1671 627 727 881 639 49 1837 737 49 1528 1671 1226 627 727 1837 608 1585 1933 737 737 1837 842 880 1755 47 28 1755 28 1671 880 28 1387 1528 608 608 1159 1755 1154 1249 639 1528 371 1987 47 881 1243 842 639 637 1154 1528 49 627 1243 1226 1528 637 1159 18...

result:

ok Accepted.

Test #7:

score: 0
Accepted
time: 1752ms
memory: 657804kb

input:

1999 1998 32159
467 1459
467 522
467 1297
467 1095
1751 467
1347 467
1771 467
1939 467
467 589
467 782
467 1947
11 467
467 1008
1841 467
467 615
467 1837
467 999
467 1674
572 467
1204 467
926 467
659 467
1579 467
467 1663
533 467
467 491
996 467
467 1355
467 596
530 467
467 1205
642 467
676 467
1206...

output:

-1

result:

ok Accepted.

Subtask #2:

score: 0
Wrong Answer

Test #8:

score: 15
Accepted
time: 0ms
memory: 12092kb

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:

10 10 10 10 2 10 8 2 1 10 

result:

ok Accepted.

Test #9:

score: -15
Wrong Answer
time: 2ms
memory: 12144kb

input:

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

output:

-1

result:

wrong answer jury find the answer, but you don't.

Subtask #3:

score: 0
Wrong Answer

Test #19:

score: 0
Wrong Answer
time: 33ms
memory: 36996kb

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:

-1

result:

wrong answer jury find the answer, but you don't.

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #3:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #5:

0%