QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#267555 | #7869. 建设终末树 | 275307894a | 20 | 679ms | 174336kb | C++14 | 4.1kb | 2023-11-27 14:21:56 | 2023-11-27 14:21:58 |
Judging History
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%