QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#268163 | #7869. 建设终末树 | grass8cow | 10 | 1532ms | 674784kb | C++17 | 3.8kb | 2023-11-28 11:55:37 | 2023-11-28 11:55:38 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m,q,N,O;
#define pb push_back
int ans[4010000];
struct DSU{
int fa[2010];
inline void build(){for(int i=1;i<=m;i++)fa[i]=i;}
int F(int x){if(x==fa[x])return x;return fa[x]=F(fa[x]);}
inline bool mer(int u,int v){u=F(u),v=F(v);if(u==v)return 0;fa[u]=v;return 1;}
}wc[2010];
void ad(DSU &a,DSU b){for(int i=1;i<=m;i++)if(b.fa[i]!=i)a.mer(b.fa[i],i);}
namespace SAT2{
int hd[16010000],nxt[44010000],to[44010000],sta[16010010],col[16001000],cn,scc;
int dfn[16001000],low[16001000],top;bool vis[16001000];
void add(int u,int v){nxt[++cn]=hd[u],to[cn]=v,hd[u]=cn;}
void dfs(int x){
dfn[x]=low[x]=++dfn[0],sta[++top]=x,vis[x]=1;
for(int i=hd[x];i;i=nxt[i]){
int v=to[i];
if(!dfn[v])dfs(v),low[x]=min(low[x],low[v]);
else if(vis[v])low[x]=min(low[x],dfn[v]);
}
if(dfn[x]==low[x]){
col[x]=++scc,vis[x]=0;
while(sta[top]!=x)col[sta[top]]=scc,vis[sta[top]]=0,top--;
top--;
}
}
void sol(){
for(int i=1;i<=O;i++)if(!dfn[i])dfs(i);
for(int i=1;i<=N;i++){
if(col[i]==col[i+N]){puts("-1");exit(0);}
ans[i]=(col[i]<col[i+N])?0:1;
}
}
}
int id[2010][2010];
vector<int>g[2010];int jr[2010];
vector<int>gg[501000],gv[501000],gc[2010];
namespace Tree{
int f[2010][20],d[2010],bel[2010];
void dfs(int x){
bel[++bel[0]]=x;
for(int v:g[x])if(v!=jr[x]){
jr[v]=f[v][0]=x;for(int i=1;i<20;i++)f[v][i]=f[f[v][i-1]][i-1];
d[v]=d[x]+1,dfs(v);
}
}
int lca(int u,int v){
if(d[u]<d[v])swap(u,v);int a=d[u]-d[v];
for(int i=10;i>=0;i--)if((a>>i)&1)
u=f[u][i];if(u==v)return u;
for(int i=10;i>=0;i--)if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
return f[u][0];
}
int sz[2010];
void pf(int o){
memset(sz,0,sizeof(sz));int ii,uu;scanf("%d",&ii);for(int i=0;i<ii;i++)
scanf("%d",&uu),sz[uu]=1;
for(int i=n;i>=2;i--)sz[jr[bel[i]]]+=sz[bel[i]];
for(int i=2;i<=n;i++){
if(!sz[i])SAT2::add(id[i][o],id[i][o]+N);
if(sz[i]==ii)SAT2::add(id[i][o]+N,id[i][o]);
}
for(int i=1;i<=n;i++){
int hm=(int)g[i].size();
if(hm==1)continue;
for(int j=0;j+1<hm;j++){
int v=g[i][j];
O++,SAT2::add(O,(v!=jr[i])?(id[v][o]+N):id[i][o]);
int v2=g[i][j+1];
SAT2::add((v2!=jr[i])?id[v2][o]:(id[i][o]+N),O);
if(j)SAT2::add(O,O-1);
}
for(int j=hm-1;j;j--){
int v=g[i][j];
O++,SAT2::add(O,(v!=jr[i])?(id[v][o]+N):id[i][o]);
int v2=g[i][j-1];
SAT2::add((v2!=jr[i])?id[v2][o]:(id[i][o]+N),O);
if(j!=hm-1)SAT2::add(O,O-1);
}
}
}
void push(){
for(int i=1;i<=n;i++)bel[i]=i;
sort(bel+1,bel+n+1,[&](int x,int y){return d[x]<d[y];});
for(int i=1;i<=n;i++)for(int j:gc[i]){
int fi=gg[j][0];
for(int x:gv[j])for(int y:gg[j]){
int u=x;
while(u!=i){
if(!wc[u].mer(fi,y))break;
u=jr[u];
}
}
}
}
}
bool np[2010];
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=2;i<=n;i++)for(int j=1;j<=m;j++)id[i][j]=(i-2)*m+j;
for(int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
g[u].pb(v),g[v].pb(u);
}
Tree::dfs(1);
N=(n-1)*m;O=N*2;
for(int i=1;i<=m;i++)Tree::pf(i);
for(int i=2;i<=n;i++)wc[i].build();
for(int i=1,st,sm;i<=q;i++){
int lc;scanf("%d",&st);
for(int j=1,v;j<=st;j++){
scanf("%d",&v);
if(j==1)lc=v;else lc=Tree::lca(lc,v);
gv[i].pb(v);
}
scanf("%d",&sm);for(int j=1,og;j<=sm;j++)scanf("%d",&og),gg[i].pb(og);
gc[lc].pb(i);
}
Tree::push();
for(int i=2;i<=n;i++)for(int j=1;j<=m;j++)if(wc[i].fa[j]!=j){
int u=id[i][j],v=id[i][wc[i].fa[j]];
SAT2::add(u,v),SAT2::add(v,u);
SAT2::add(u+N,v+N),SAT2::add(v+N,u+N);
}
SAT2::sol();
for(int i=1;i<=m;i++){
memset(np,0,sizeof(np));
for(int j=2;j<=n;j++){if(ans[id[j][i]])np[j]=1;else np[jr[j]]=1;}
int rt=-1;
for(int j=1;j<=n;j++)if(!np[j])rt=j;
printf("%d ",rt);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1532ms
memory: 662692kb
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: 1481ms
memory: 667452kb
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: 1499ms
memory: 674784kb
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: 1493ms
memory: 652848kb
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: 1517ms
memory: 661552kb
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: 1460ms
memory: 664148kb
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: 1489ms
memory: 666056kb
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: 43412kb
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: 0ms
memory: 40676kb
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 2 9 3 8 3 9 4
result:
ok Accepted.
Test #10:
score: 0
Accepted
time: 6ms
memory: 41284kb
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 3 9 10 10 3 3 3
result:
ok Accepted.
Test #11:
score: 0
Accepted
time: 3ms
memory: 40868kb
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: 0ms
memory: 39736kb
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 2 2 7 7 7 2 7 7 7
result:
ok Accepted.
Test #13:
score: 0
Accepted
time: 5ms
memory: 40568kb
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:
2 4 4 4 4 2 2 2 2 4
result:
ok Accepted.
Test #14:
score: 0
Accepted
time: 0ms
memory: 40268kb
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:
10 10 10 10 10 5 10 2 2 10
result:
ok Accepted.
Test #15:
score: -15
Wrong Answer
time: 0ms
memory: 41124kb
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:
3 5 6 3 6 3 6 3 6 5
result:
wrong answer restrict 1 is not satisfied.
Subtask #3:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 75ms
memory: 87228kb
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 466 48 259 122 253 1 500 71 297 361 471 36 104 242 25 390 305 390 469 369 74 309 415 133 494 429 231 425 74 389 47 429 211 74 296 2 341 253 275 174 1 378 452 74 29 132 266 213 4 47 1 21 479 342 390 375 207 365 2 472 378 253 435 92 122 350 431 322 104 47...
result:
wrong answer restrict 546 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:
100%
Accepted
Dependency #5:
0%