QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#267026 | #7869. 建设终末树 | zyz07 | 0 | 2129ms | 698440kb | C++17 | 6.5kb | 2023-11-26 21:27:17 | 2023-11-26 21:27:18 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(auto Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(auto Ti=(Ta);Ti>=(Tb);--Ti)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
using ll=long long;
const int N=2005,V=N*N*4;
int n,m,q,tag[N],cnt[N],fa[N],fai[N];
vector<pair<int,int>> e[N];
vector<int> A[N];
void get_fa(int u){
for(auto [v,i]:e[u]){
if(v!=fa[u]){
fa[v]=u;
fai[v]=i;
get_fa(v);
}
}
}
int siz[N],dep[N],hson[N];
void dfs1(int u){
siz[u]=1;
dep[u]=dep[fa[u]]+1;
for(auto [v,i]:e[u]){
if(v!=fa[u]){
dfs1(v);
siz[u]+=siz[v];
if(siz[v]>siz[hson[u]]){
hson[u]=v;
}
}
}
}
int dfn[N],rk[N],dfx,top[N];
void dfs2(int u,int tp){
rk[dfn[u]=++dfx]=u;
top[u]=tp;
if(hson[u]){
dfs2(hson[u],tp);
}
for(auto [v,i]:e[u]){
if(v!=fa[u]&&v!=hson[u]){
dfs2(v,v);
}
}
}
// 0 -> up, 1 -> down
// i: edge, j: item
int id(int i,int j,bool one){
return (j-1)*(n-1)+i+one*m*(n-1);
}
int tot;
template<int N>
struct DSU{
int n,fa[N];
void init(int _n){
n=_n;
For(i,1,n) fa[i]=i;
}
int find(int u){
for(;u!=fa[u];u=fa[u]=fa[fa[u]]);
return u;
}
bool merge(int u,int v){
u=find(u);
v=find(v);
fa[u]=v;
return u!=v;
}
};
DSU<N*N> dsu;
struct Edge{
int v,nxt;
}edg[int(3e7)];
int bel[V],head[V],ecnt;
void add_edge(int u,int v){
u=bel[u];
v=bel[v];
edg[++ecnt]={v,head[u]};
head[u]=ecnt;
}
void dfs(int u,int i,int len){
cnt[u]=(tag[u]==i);
for(auto [v,_]:e[u]){
if(v!=fa[u]){
dfs(v,i,len);
cnt[u]+=cnt[v];
}
}
if(u>1){
if(!cnt[u]){
add_edge(id(fai[u],i,1),id(fai[u],i,0));
}else if(cnt[u]==len){
add_edge(id(fai[u],i,0),id(fai[u],i,1));
}
}
}
struct Two_Sat{
struct Vert{
int dfn,low,bel;
bool in;
}t[V];
int dfx,scc_cnt,stk[V],top;
void tarjan(int u){
t[u].dfn=t[u].low=++dfx;
stk[++top]=u;
t[u].in=1;
for(int i=head[u];i;i=edg[i].nxt){
int v=edg[i].v;
if(!t[v].dfn){
tarjan(v);
t[u].low=min(t[u].low,t[v].low);
}else if(t[v].in){
t[u].low=min(t[u].low,t[v].dfn);
}
}
if(t[u].low==t[u].dfn){
++scc_cnt;
while(1){
int v=stk[top--];
t[v].bel=scc_cnt;
t[v].in=0;
if(v==u) break;
}
}
}
void solve(){
For(i,1,tot){
if(!t[i].dfn){
tarjan(i);
}
}
}
}sat;
int color(int u){
return sat.t[bel[u]].bel;
}
struct Rollback_DSU{
int fa[N],siz[N];
vector<int> op;
int find(int u){
return u==fa[u]?u:find(fa[u]);
}
void init(){
For(i,1,m){
fa[i]=i;
siz[i]=1;
}
}
void merge(int u,int v){
u=find(u);
v=find(v);
if(u!=v){
if(siz[u]<siz[v]){
swap(u,v);
}
fa[v]=u;
siz[u]+=siz[v];
op.push_back(v);
}
}
void undo(unsigned ver){
while(op.size()>ver){
int v=op.back();
op.pop_back();
siz[fa[v]]-=siz[v];
fa[v]=v;
}
}
}dsu2;
struct Segment_Tree{
vector<pair<int,int>> ins[N*4];
DSU<N> dsu[N*4];
void init(int p=1,int L=2,int R=n){
dsu[p].init(m);
if(L==R) return;
int mid=(L+R)/2;
init(p*2,L,mid);
init(p*2+1,mid+1,R);
}
void range_link(int l,int r,int u,int v,int p=1,int L=2,int R=n){
if(l<=L&&R<=r){
if(dsu[p].merge(u,v)){
ins[p].emplace_back(dsu[p].find(u),dsu[p].find(v));
}
return;
}
int mid=(L+R)/2;
if(l<=mid) range_link(l,r,u,v,p*2,L,mid);
if(r>mid) range_link(l,r,u,v,p*2+1,mid+1,R);
}
void iterate(int p=1,int L=2,int R=n){
auto ver=dsu2.op.size();
for(auto [u,v]:ins[p]){
dsu2.merge(u,v);
}
if(L==R){
if(L>1){
int i=fai[rk[L]];
For(j,1,m){
int k=dsu2.find(j);
if(j!=k){
::dsu.merge(id(i,k,0),id(i,j,0));
}
}
}
dsu2.undo(ver);
return;
}
int mid=(L+R)/2;
iterate(p*2,L,mid);
iterate(p*2+1,mid+1,R);
dsu2.undo(ver);
}
}seg;
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
// assert(freopen("B.in","r",stdin));
// assert(freopen("B.out","w",stdout));
cin>>n>>m>>q;
For(i,1,n-1){
int u,v;
cin>>u>>v;
e[u].emplace_back(v,i);
e[v].emplace_back(u,i);
}
get_fa(1);
dfs1(1);
dfs2(1,1);
tot=m*(n-1)*2;
For(i,1,m){
int len;
cin>>len;
A[i].resize(len);
For(j,0,len-1) cin>>A[i][j];
}
dsu.init(m*(n-1));
seg.init();
For(_,1,q){
vector<int> V,S;
int lV,lS;
cin>>lV;
V.resize(lV);
For(i,0,lV-1) cin>>V[i];
cin>>lS;
S.resize(lS);
For(i,0,lS-1) cin>>S[i];
sort(range(V),[](int u,int v){
return dfn[u]<dfn[v];
});
auto merge=[&](int u,int v,int i,int j){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]){
swap(u,v);
}
seg.range_link(dfn[top[u]],dfn[u],i,j);
u=fa[top[u]];
}
if(u!=v){
if(dfn[u]<dfn[v]){
swap(u,v);
}
seg.range_link(dfn[v]+1,dfn[u],i,j);
}
};
For(i,0,lS-2){
For(j,0,lV-1){
merge(V[j],V[(j+1)%lV],S[i],S[i+1]);
}
}
}
dsu2.init();
seg.iterate();
{
int x=m*(n-1);
For(i,1,x){
bel[i]=dsu.find(i);
}
For(i,x+1,x*2){
bel[i]=bel[i-x]+x;
}
For(i,x*2+1,x*4){
bel[i]=i;
}
}
debug("%d\n",int(clock()));
For(i,1,m){
for(int u:A[i]){
tag[u]=i;
}
dfs(1,i,A[i].size());
vector<int> pre(n+1),suf(n+1);
For(u,1,n){
int cur=0;
for(auto [v,j]:e[u]){
if(v!=fa[u]){
pre[v]=cur;
if(cur){
++tot;
add_edge(tot,cur);
add_edge(tot,id(j,i,0));
cur=tot;
}else{
cur=id(j,i,0);
}
}
}
reverse(range(e[u]));
cur=0;
for(auto [v,j]:e[u]){
if(v!=fa[u]){
suf[v]=cur;
if(cur){
++tot;
add_edge(tot,cur);
add_edge(tot,id(j,i,0));
cur=tot;
}else{
cur=id(j,i,0);
}
}
}
reverse(range(e[u]));
for(auto [v,j]:e[u]){
if(v!=fa[u]){
if(u>1){
add_edge(id(j,i,1),id(fai[u],i,1));
}
if(pre[v]){
add_edge(id(j,i,1),pre[v]);
}
if(suf[v]){
add_edge(id(j,i,1),suf[v]);
}
}else if(cur){
add_edge(id(j,i,0),cur);
}
}
}
}
debug("tot=%d,ecnt=%d\n",tot,ecnt);
debug("%d\n",int(clock()));
sat.solve();
debug("%d\n",int(clock()));
For(i,1,n-1){
For(j,1,m){
if(color(id(i,j,0))==color(id(i,j,1))){
cout<<"-1\n";
return 0;
}
}
}
For(j,1,m){
For(u,1,n){
bool flg=1;
for(auto [v,i]:e[u]){
flg&=(color(id(i,j,1))<color(id(i,j,0)))==(v==fa[u]);
}
if(flg){
cout<<u<<' ';
break;
}
}
}
cout<<'\n';
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: 2129ms
memory: 698440kb
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 1 1 233 1 233 233 1 1 233 233 1 233 1 233 233 233 233 1 233 233 233 233 1 233 1 1 1 1 233 1 233 233 233 233 1 1 233 233 233 1 233 233 1 233 1 233 1 1 899 1 1 233 233 233 1 233 233 233 233 1 233 1 1 233 233 233 1 1 233 233 1 233 233 233 233 1 1 1 233 233 233 233 1 1 1 1 233 233 233 233 233 1 233 23...
result:
wrong answer restrict 3 is not satisfied.
Subtask #2:
score: 0
Wrong Answer
Test #8:
score: 0
Wrong Answer
time: 2ms
memory: 12504kb
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 4 4 2 4 8 2 1 10
result:
wrong answer restrict 1 is not satisfied.
Subtask #3:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 25ms
memory: 42336kb
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 263 387 434 163 4 212 216 174 274 398 168 385 326 1 454 302 1 453 1 477 149 52 361 44 36 104 75 25 278 353 280 447 1 74 31 287 1 89 270 304 1 224 421 109 429 346 495 193 381 406 119 206 174 1 219 452 488 305 371 83 213 311 42 1 276 387 1 5 282 498 29 471 472 251 120 1 70 1 1 431 322 37 241 404 3...
result:
wrong answer restrict 1 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:
0%