QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#267555#7869. 建设终末树275307894a20 679ms174336kbC++144.1kb2023-11-27 14:21:562023-11-27 14:21:58

Judging History

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

  • [2023-11-27 14:21:58]
  • 评测
  • 测评结果:20
  • 用时:679ms
  • 内存:174336kb
  • [2023-11-27 14:21:56]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=2e3+5,M=N*N+5,K=(1<<25)+5,mod=1e9+7,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n,m,q,x,y,z,id[N][N],Ct;vector<int> S[N];
struct yyy{int to,z;};struct ljb{int head,h[N*N];yyy f[N*N*4];void add(int x,int y){f[++head]=(yyy){y,h[x]};h[x]=head;/*cerr<<x<<' '<<y<<'\n';*/}}s;
int fa[N],d[N],tp[N],siz[N],son[N],is[N],df[N],ih;
int g[N];
int ans[N][N],vis[N][N];
void dfs1(int v,int La,int is){
	for(int i:S[v]) if(i^La) dfs1(i,v,is),g[v]+=g[i];
	if(!g[v]) ans[is][v]=1;
	else if(g[v]==x&&v^1) ans[is][v]=0;
	// else cerr<<v<<' '<<g[v]<<'\n';
}
int f[N][N];
int GF(int x,int *fa){return fa[x]^x?fa[x]=GF(fa[x],fa):x;}
vector<int> scs;
namespace Tree{
	#define ls v<<1
	#define rs v<<1|1
	int fa[N*4][N];
	void build(int l=1,int r=n,int v=1){
		iota(fa[v]+1,fa[v]+m+1,1);if(l==r) return;
		int m=l+r>>1;build(l,m,ls);build(m+1,r,rs);
	}
	void add(int x,int y,int l=1,int r=n,int v=1){
		// cerr<<x<<' '<<y<<' '<<z1<<' '<<z2<<'\n';
		if(x<=l&&r<=y) {scs.emplace_back(v);return;}
		int m=l+r>>1;x<=m&&(add(x,y,l,m,ls),0);y>m&&(add(x,y,m+1,r,rs),0);
	}
	void push(int l=1,int r=n,int v=1){
		if(l==r) {Mc(f[df[l]],fa[v]);return;}
		for(int i=1;i<=m;i++) if(GF(i,fa[v])^i){
			fa[ls][GF(i,fa[ls])]=GF(fa[v][i],fa[ls]);
			fa[rs][GF(i,fa[rs])]=GF(fa[v][i],fa[rs]);
		}
		int m=l+r>>1;push(l,m,ls);push(m+1,r,rs);
	}
	void merge(int v,int z1,int z2){fa[v][GF(z1,fa[v])]=GF(z2,fa[v]);}
}
void make1(int x,int La){
	fa[x]=La;d[x]=d[La]+1;siz[x]=1;
	for(int i:S[x]) if(i^La) make1(i,x),siz[x]+=siz[i],siz[i]>siz[son[x]]&&(son[x]=i);
}
void make2(int x,int La){
	tp[x]=La;is[x]=++ih;df[ih]=x;if(son[x]) make2(son[x],La);
	for(int i:S[x]) if(i^fa[x]&&i^son[x]) make2(i,i);
}
int LCA(int x,int y){
	while(tp[x]^tp[y]) d[tp[x]]<d[tp[y]]&&(swap(x,y),0),x=fa[tp[x]];
	return d[x]<d[y]?x:y;
}
void merge(int x,int y){
	// cerr<<z1<<' '<<z2<<' '<<x<<' '<<y<<'\n';
	while(tp[x]^tp[y]) Tree::add(is[tp[y]],is[y]),y=fa[tp[y]];
	if(x^y) Tree::add(is[x]+1,is[y]);
}
void tarjan(int x,int y,int w){
	// cerr<<x<<' '<<y<<' '<<w<<'\n';
	if(~ans[x][y]&&ans[x][y]^w){puts("-1");exit(0);}
	if(vis[x][y]) return;vis[x][y]=1;ans[x][y]=w;
	for(int j=s.h[id[x][y]],i=s.f[j].to;j;j=s.f[j].z,i=s.f[j].to) tarjan(i,y,w);
	if(w){
		for(int i:S[y]) if(i^fa[y]) tarjan(x,i,1);
	}else{
		for(int i:S[fa[y]]) if(i^y) tarjan(x,i,i!=fa[fa[y]]);
	}
}
void Solve(){
	int i,j;scanf("%d%d%d",&n,&m,&q);
	for(i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		S[x].emplace_back(y);S[y].emplace_back(x);
	}
	for(i=1;i<=m;i++) for(j=1;j<=n;j++) id[i][j]=++Ct,ans[i][j]=-1;
	for(i=1;i<=m;i++){
		Me(g,0);scanf("%d",&x);
		for(j=1;j<=x;j++) scanf("%d",&y),g[y]++;
		dfs1(1,0,i);
	}
	make1(1,0);make2(1,1);Tree::build();
	while(q--){
		scanf("%d",&x);vector<int> c1(x);for(i=0;i<x;i++) scanf("%d",&c1[i]);
		int Ls=c1.front();for(int i:c1) Ls=LCA(Ls,i);
		scs.clear();for(int i:c1) merge(Ls,i);
		scanf("%d",&x);int La=0;
		while(x--){
			int y;scanf("%d",&y);
			if(!La){La=y;continue;}
			for(int i:scs) Tree::merge(i,La,y); 
		}
	}
	Tree::push();
	for(i=2;i<=n;i++) for(j=1;j<=m;j++) if(GF(j,f[i])^j){
		// cerr<<j<<' '<<i<<' '<<GF(j,f[i])<<'\n';
		s.add(id[j][i],f[i][j]),s.add(id[f[i][j]][i],j);
	}
	for(i=1;i<=m;i++) for(j=2;j<=n;j++) if(~ans[i][j]) tarjan(i,j,ans[i][j]);
	for(i=1;i<=m;i++) for(j=2;j<=n;j++) if(ans[i][j]==-1) tarjan(i,j,1);
	for(i=1;i<=m;i++) {
		for(j=1;j<=n;j++) {
			int flag=0;for(int h:S[j]) flag|=ans[i][d[h]<d[j]?j:h]^(h!=fa[j]);
			if(!flag) printf("%d ",j);
			// cerr<<i<<' '<<j<<' '<<ans[i][j]<<' '<<flag<<'\n';
		}
	}
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 679ms
memory: 174336kb

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

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #8:

score: 15
Accepted
time: 2ms
memory: 14176kb

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: 0
Accepted
time: 2ms
memory: 14076kb

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:

7 8 9 1 9 1 8 3 9 3 

result:

ok Accepted.

Test #10:

score: 0
Accepted
time: 0ms
memory: 14060kb

input:

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

output:

9 3 10 2 9 10 10 3 3 1 

result:

ok Accepted.

Test #11:

score: 0
Accepted
time: 2ms
memory: 13840kb

input:

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

output:

-1

result:

ok Accepted.

Test #12:

score: 0
Accepted
time: 2ms
memory: 14112kb

input:

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

output:

7 7 7 7 7 1 7 7 1 7 

result:

ok Accepted.

Test #13:

score: 0
Accepted
time: 2ms
memory: 14172kb

input:

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

output:

1 4 4 4 1 1 1 4 1 4 

result:

ok Accepted.

Test #14:

score: 0
Accepted
time: 0ms
memory: 14084kb

input:

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

output:

1 1 10 1 1 5 1 1 10 1 

result:

ok Accepted.

Test #15:

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

input:

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

output:

-1

result:

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

Subtask #3:

score: 20
Accepted

Test #19:

score: 20
Accepted
time: 21ms
memory: 42248kb

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 368 6 72 163 77 212 74 6 269 322 74 74 359 243 48 373 1 92 1 500 71 161 361 455 36 104 161 25 390 305 390 469 369 74 309 415 366 239 429 352 425 74 389 47 429 161 74 161 161 341 92 275 174 1 378 452 74 29 485 266 213 4 47 1 21 479 342 390 375 207 365 161 472 378 92 435 352 1 350 431 322 104 479 ...

result:

ok Accepted.

Test #20:

score: 0
Accepted
time: 17ms
memory: 42368kb

input:

500 500 5000
297 429
444 310
304 235
470 8
33 395
174 34
276 320
298 478
149 117
400 211
118 399
448 268
446 484
268 180
465 471
68 443
33 358
256 431
490 452
110 389
304 418
286 219
498 16
416 376
495 173
408 138
473 228
317 199
344 279
31 469
159 16
377 397
492 402
308 107
461 11
332 105
377 77
31...

output:

39 252 124 376 250 200 48 31 336 117 179 31 481 203 415 380 65 292 114 244 60 6 15 60 357 441 370 279 296 38 41 65 250 133 1 463 65 179 387 79 446 489 405 83 357 376 472 65 223 371 354 265 481 280 377 74 87 70 171 481 436 471 203 163 237 409 65 13 114 280 249 321 65 481 13 416 348 110 357 1 306 380 ...

result:

ok Accepted.

Test #21:

score: 0
Accepted
time: 12ms
memory: 39796kb

input:

499 498 5000
28 246
54 26
13 312
346 225
377 80
274 410
352 446
394 386
204 453
54 355
337 480
313 263
90 395
388 61
193 71
213 265
125 121
65 120
154 216
331 206
475 413
263 332
322 306
75 290
335 222
149 360
89 139
52 10
91 132
202 88
211 106
205 422
19 467
250 156
382 223
161 486
4 8
495 16
64 12...

output:

147 176 188 490 374 147 62 438 354 405 442 472 495 33 117 374 269 136 1 211 369 176 442 438 441 47 24 221 98 405 277 251 467 172 136 6 475 1 314 62 377 166 1 107 305 200 344 1 229 136 71 200 10 369 78 301 6 1 221 200 438 172 48 358 458 135 7 395 254 188 133 405 274 200 298 412 117 200 200 355 342 39...

result:

ok Accepted.

Test #22:

score: 0
Accepted
time: 18ms
memory: 39472kb

input:

499 500 5000
71 225
374 470
413 420
422 368
357 141
479 360
172 237
21 40
16 386
434 274
188 207
249 16
9 259
152 63
488 264
166 467
51 70
90 417
209 411
43 101
102 206
320 29
110 408
182 333
115 394
138 458
29 296
73 241
392 145
235 428
197 114
271 125
131 401
122 377
215 252
186 253
38 309
11 491
...

output:

66 299 264 133 346 22 322 2 378 141 4 497 29 2 133 378 2 2 29 378 108 4 108 421 378 4 390 421 29 346 323 2 322 497 141 312 295 421 2 66 21 497 422 2 497 390 422 497 108 497 264 422 378 22 390 295 467 93 29 113 497 2 22 422 312 264 312 497 22 21 322 93 21 299 29 21 4 22 312 2 322 497 22 29 93 141 93 ...

result:

ok Accepted.

Test #23:

score: 0
Accepted
time: 17ms
memory: 39432kb

input:

498 498 5000
181 300
371 226
361 224
82 101
233 476
366 273
212 240
90 169
488 477
22 374
164 369
276 390
350 61
101 165
331 274
72 325
371 190
472 404
250 449
179 451
64 153
447 267
97 24
495 168
139 170
203 407
493 225
413 216
29 490
306 332
257 309
43 279
189 94
294 287
297 319
289 406
221 338
74...

output:

178 489 439 71 71 326 44 448 270 71 274 8 63 145 8 71 96 326 274 178 109 437 491 391 437 326 96 140 63 343 270 437 439 489 274 224 178 491 324 185 448 270 391 8 251 489 437 274 491 97 473 124 8 97 343 491 8 44 473 124 491 63 391 178 489 97 448 343 489 324 448 185 185 439 489 489 489 178 437 391 71 2...

result:

ok Accepted.

Test #24:

score: 0
Accepted
time: 16ms
memory: 39748kb

input:

498 499 5000
49 110
380 351
80 59
60 4
378 224
383 28
95 381
220 227
287 440
251 493
278 388
157 339
489 377
98 308
122 403
267 47
109 207
140 31
461 264
210 481
130 216
31 410
383 9
141 13
343 448
45 324
297 449
371 149
474 214
41 154
185 138
299 34
412 411
492 327
277 229
33 494
237 12
97 420
6 18...

output:

187 412 483 390 412 483 93 483 412 483 483 390 412 483 483 412 483 93 412 93 187 412 187 483 431 93 187 483 390 187 93 483 390 390 390 93 187 390 483 187 93 187 93 390 187 187 187 187 412 483 187 483 187 483 187 483 483 390 187 93 483 412 412 187 483 412 483 187 412 390 483 390 483 187 412 390 93 41...

result:

ok Accepted.

Test #25:

score: 0
Accepted
time: 23ms
memory: 40636kb

input:

500 499 5000
368 181
285 335
445 454
267 331
22 212
294 281
454 121
19 31
57 14
101 152
130 284
329 396
406 500
446 115
337 61
421 68
203 119
352 238
313 450
16 259
167 307
326 255
173 256
77 42
203 270
249 402
153 135
146 450
172 73
185 149
398 15
426 213
407 368
351 124
159 356
371 418
319 156
304...

output:

355 210 461 415 461 210 210 415 355 461 461 19 461 487 487 461 19 355 415 461 415 487 355 487 487 487 415 487 355 487 210 487 210 210 355 355 487 461 487 355 19 355 355 487 210 487 487 415 355 461 210 355 487 415 487 487 487 487 19 355 19 461 461 487 461 19 224 210 210 210 461 355 19 461 210 461 210...

result:

ok Accepted.

Test #26:

score: 0
Accepted
time: 6ms
memory: 40516kb

input:

500 499 5000
350 140
294 337
407 172
180 28
139 287
2 413
498 218
4 449
245 412
45 247
397 482
427 165
202 490
53 323
178 209
247 341
253 485
478 203
34 305
306 173
111 14
188 64
213 9
278 59
347 454
83 448
356 336
148 239
378 272
145 402
457 189
299 209
291 368
96 110
187 270
218 304
358 217
6 455
...

output:

-1

result:

ok Accepted.

Test #27:

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

input:

499 499 5000
75 164
439 163
466 334
370 484
25 201
107 165
250 122
355 17
411 164
169 9
463 497
428 442
93 50
7 326
15 207
479 112
454 391
329 96
127 290
1 2
99 347
39 84
407 405
147 271
57 298
472 129
195 377
296 35
441 440
232 176
388 92
325 198
425 267
23 100
487 433
78 416
193 365
348 352
324 28...

output:

-1

result:

ok Accepted.

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #3:

100%
Accepted

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%