QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#265907 | #7869. 建设终末树 | grass8cow | 0 | 1409ms | 719696kb | C++17 | 4.7kb | 2023-11-25 22:19:53 | 2023-11-25 22:19:53 |
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],sz[2010];
inline void build(){for(int i=1;i<=m;i++)fa[i]=i,sz[i]=1;}
int F(int x){if(x==fa[x])return x;return fa[x]=F(fa[x]);}
inline void mer(int u,int v){u=F(u),v=F(v);if(u==v)return;if(sz[u]<sz[v])swap(u,v);fa[v]=u,sz[u]+=sz[v];}
}wc[2010],fz[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];
int gg[500100][70],sg[501000];
struct ed{int u,v,i;};
vector<ed>T[20];
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);
}
}
}
}
namespace DFZ{
bool vis[2010];int sz[2010],fa[2010];
int S,rt,mx;
void dfs(int x,int f){
sz[x]=1;int mm=-1;
for(int v:g[x])if(v!=f&&!vis[v])dfs(v,x),sz[x]+=sz[v],mm=max(mm,sz[v]);
mm=max(mm,S-sz[x]);
if(mm<mx)mx=mm,rt=x;
}
int d[2010],f[2010][20],D,be[2010][20],sg[20];
void dfs2(int x){
sg[D]++,be[sg[D]][D]=x,sz[x]=1;
for(int v:g[x])if(v!=f[x][D]&&!vis[v])f[v][D]=x,dfs2(v),sz[x]+=sz[v];
}
void so(int u){
D=d[u],vis[u]=1;
dfs2(u);
for(int v:g[u])if(!vis[v])S=sz[v],mx=S+1,rt=-1,dfs(v,0),fa[rt]=u,d[rt]=d[u]+1,so(rt);
}
void ptsd(int u,int v,int w){
int a=u,b=v;while(a!=b){if(d[a]<d[b])swap(a,b);a=fa[a];}
T[d[a]].push_back((ed){u,v,w});
}
void build(){memset(vis,0,sizeof(vis)),S=n,mx=n+1,dfs(1,0);so(rt);}
void push(){
for(int i=0;i<13;i++)if(!T[i].empty()){
for(int j=1;j<=n;j++)fz[j].build();
for(ed t:T[i]){
int w=t.i,fi=gg[w][1];
for(int j=2;j<=sg[w];j++)fz[t.u].mer(fi,gg[w][j]),fz[t.v].mer(fi,gg[w][j]);
}
for(int j=sg[i];j>=1;j--){
int u=be[j][i];
if(f[u][i]&&f[u][i]!=u){
ad(fz[f[u][i]],fz[u]);
ad(wc[(jr[u]==f[u][i])?u:f[u][i]],fz[u]);
}
}
}
}
}
int va[60];
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].push_back(v),g[v].push_back(u);
}
Tree::dfs(1),DFZ::build();
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;i<=q;i++){
scanf("%d",&st);for(int j=1;j<=st;j++)scanf("%d",&va[j]);
scanf("%d",&sg[i]);
for(int j=1;j<=sg[i];j++)scanf("%d",&gg[i][j]);
for(int j=2;j<=st;j++)DFZ::ptsd(va[1],va[j],i);
}
DFZ::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: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1409ms
memory: 719696kb
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: 0
Wrong Answer
time: 0ms
memory: 22100kb
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:
2 2 10 10 2 4 8 2 1 10
result:
wrong answer restrict 3 is not satisfied.
Subtask #3:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 83ms
memory: 80844kb
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%