QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#591552 | #7869. 建设终末树 | DaiRuiChen007 | 0 | 1228ms | 765520kb | C++17 | 3.2kb | 2024-09-26 16:23:50 | 2024-09-26 16:23:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2005;
namespace SAT {
const int MAXV=1.6e7+5;
vector <int> G[MAXV];
int dfn[MAXV],low[MAXV],dcnt,col[MAXV],scnt,stk[MAXV],tp;
bool ins[MAXV];
void link(int u,int x,int v,int y) { G[u*2+x].push_back(v*2+y); }
void tarjan(int u) {
dfn[u]=low[u]=++dcnt,stk[++tp]=u,ins[u]=true;
for(int v:G[u]) {
if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if(ins[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]) {
++scnt;
while(ins[u]) col[stk[tp]]=scnt,ins[stk[tp--]]=false;
}
}
void solve(int n) {
for(int i=0;i<2*n;++i) if(!dfn[i]) tarjan(i);
for(int i=0;i<2*n;i+=2) if(col[i]==col[i^1]) cout<<"-1\n",exit(0);
}
bool qry(int u) { return col[u<<1]>col[u<<1|1]; }
}
using SAT::link;
struct DSU {
int dsu[MAXN];
void init(int n) { iota(dsu+1,dsu+n+1,1); }
int find(int x) { return dsu[x]^x?dsu[x]=find(dsu[x]):x; }
bool merge(int u,int v) {
u=find(u),v=find(v);
if(u==v) return false;
return dsu[u]=v,true;
}
} Q[MAXN];
vector <int> G[MAXN];
int n,m,q,dfn[MAXN],fa[MAXN],dcnt,st[MAXN][20],w[MAXN][MAXN];
vector <int> od,rod;
void dfs(int u,int fz) {
dfn[u]=++dcnt,st[dcnt][0]=fa[u]=fz,od.push_back(u);
for(int v:G[u]) if(v^fz) dfs(v,u);
}
int cmp(int u,int v) { return dfn[u]<dfn[v]?u:v; }
int bit(int x) { return 1<<x; }
int LCA(int x,int y) {
if(x==y) return x;
int l=min(dfn[x],dfn[y])+1,r=max(dfn[x],dfn[y]),k=__lg(r-l+1);
return cmp(st[l][k],st[r-bit(k)+1][k]);
}
vector <array<int,3>> Z[MAXN];
int id[MAXN][MAXN],pre[MAXN];
signed main() {
ios::sync_with_stdio(false);
cin>>n>>m>>q;
for(int i=1,u,v;i<n;++i) {
cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
}
for(int i=2;i<=n;++i) Q[i].init(m);
dfs(1,0),rod=od;
reverse(rod.begin(),rod.end());
for(int k=1;k<20;++k) for(int i=1;i+bit(k)-1<=n;++i) {
st[i][k]=cmp(st[i][k-1],st[i+bit(k-1)][k-1]);
}
for(int i=1,k;i<=m;++i) {
cin>>k;
for(int x;k--;) cin>>x,++w[i][x];
for(int x:rod) if(x^1) w[i][fa[x]]+=w[i][x];
}
for(int o=1,v,s;o<=q;++o) {
cin>>v; vector <int> V(v);
for(int &u:V) cin>>u;
cin>>s; vector <int> S(s);
for(int &u:S) cin>>u;
V.push_back(V[0]);
for(int i=1;i<=v;++i) {
int x=LCA(V[i],V[i-1]),y=V[i];
for(int j=1;j<s;++j) Z[x].push_back({y,S[j-1],S[j]});
}
}
for(int u:od) for(auto z:Z[u]) {
for(int t=z[0];t!=u&&Q[t].merge(z[1],z[2]);t=fa[t]);
}
int tot=0;
for(int i=2;i<=n;++i) for(int j=1;j<=m;++j) {
if(Q[i].find(j)==j) id[j][i]=tot++;
}
for(int i=2;i<=n;++i) for(int j=1;j<=m;++j) {
id[j][i]=id[Q[i].find(j)][i];
}
for(int o=1;o<=m;++o) {
memset(pre,-1,sizeof(pre));
for(int u:rod) if(u^1) {
int x=id[o][u];
if(!w[o][u]) link(x,1,x,0);
else if(w[o][u]==w[o][1]) link(x,0,x,1);
else {
int v=fa[u];
link(x,1,id[o][v],1);
link(id[o][v],0,x,0);
if(~pre[v]) {
link(pre[v],1,x,0);
link(x,1,pre[v],0);
link(pre[v],1,tot,1);
link(tot,0,pre[v],0);
link(x,1,tot,1);
link(tot,0,x,0);
pre[v]=tot++;
} else pre[v]=x;
}
}
}
SAT::solve(tot);
for(int o=1;o<=m;++o) {
int u=1;
for(int x:od) if(x!=1&&SAT::qry(id[o][x])) u=x;
cout<<u<<" \n"[o==m];
}
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: 1228ms
memory: 765520kb
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: 59ms
memory: 385572kb
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
Accepted
time: 55ms
memory: 385264kb
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: 15
Accepted
time: 56ms
memory: 387196kb
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: 15
Accepted
time: 70ms
memory: 385188kb
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
Wrong Answer
time: 56ms
memory: 385316kb
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:
-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: 55ms
memory: 402020kb
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:
0%