QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#594898 | #7869. 建设终末树 | byron10000 | 0 | 0ms | 0kb | C++14 | 5.4kb | 2024-09-28 11:04:24 | 2024-09-28 11:04:25 |
answer
#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_) for(int V_=(A_), V_##_END=(B_); V_>=V_##_END; V_--)
#ifdef _WIN32
#define long __int64
#endif
#if defined(_LOCAL_) && 0
#undef assert
#define assert(expr) ({ if(!(expr)) asm("int3"); 0; })
#endif
using namespace std;
const int MAXN=2010,MAXQ=5e5+10;
int n,m,qn,ans[MAXN]; vector<int> G[MAXN];
// 2 Sat
int var(int i,int x){ return i*2+x; }
int neg(int u){ return u^1; }
struct TwoSat{
static const int MAXN=1.6e7,MAXM=5.6e7;
int nnd;
struct{ int v,nxt; } E[MAXM]; int head[MAXN],ecnt;
void _add(int u,int v){ E[++ecnt]={v,head[u]},head[u]=ecnt; }
void add(int u,int v){
_add(u,v);
if(!(neg(v)==u&&neg(u)==v)) _add(neg(v),neg(u));
}
int dfn[MAXN],low[MAXN],dfnc,stk[MAXN],stkp,col[MAXN],ncol,sol[MAXN]; bool instk[MAXN];
void tarjan(int u){
dfn[u]=low[u]=++dfnc; stk[++stkp]=u,instk[u]=1;
for(int i=head[u]; i; i=E[i].nxt){
int v=E[i].v;
if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if(instk[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
col[u]=++ncol,instk[u]=0;
int v;
while((v=stk[stkp--])!=u) col[v]=ncol,instk[v]=0;
}
}
bool solve(){
RNG(u,2,2*nnd+1){
if(!dfn[u]) tarjan(u);
}
RNG(i,1,nnd){
if(col[var(i,0)]==col[var(i,1)]) return 0;
auto a=col[var(i,1)]<col[var(i,0)]; sol[var(i,0)]=!a,sol[var(i,1)]=a;
}
return 1;
}
} ts;
// Tree info
struct DSU{
int fa[MAXN];
void init(){ iota(fa+1,fa+m+1,1); }
int find(int u){ return u==fa[u]?u:fa[u]=find(fa[u]); }
void merge(int u,int v){
if((u=find(u))!=(v=find(v))) fa[v]=u;
}
} dsu[MAXN][11];
int dfn[MAXN],dfnc,fa[MAXN][11],dep[MAXN];
void dfs1(int u,int fa_){
fa[u][0]=fa_,dfn[u]=++dfnc,dep[u]=dep[fa_]+1,dsu[u][0].init();
RNG(i,1,__lg(dep[u])) fa[u][i]=fa[fa[u][i-1]][i-1],dsu[u][i].init();
for(int v:G[u]){
if(v!=fa_) dfs1(v,u);
}
}
int lca(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
int d=dep[u]-dep[v];
RNG(i,0,10){
if((d>>i)&1) u=fa[u][i];
}
if(u==v) return u;
IRNG(i,10,1){
if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
}
return fa[u][0];
}
// Merge edges
void upd(int u,int d,vector<int>& S){
if(!d||S.size()==1) return;
IRNG(i,10,0){
if((d>>i)&1){
RNG(j,1,int(S.size())-1) dsu[u][i].merge(S[0],S[j]);
u=fa[u][i];
}
}
}
void dfs2(int u){
for(auto v:G[u]){
if(v!=fa[u][0]) dfs2(v);
}
IRNG(i,__lg(dep[u]),1){
int v=fa[u][i-1];
RNG(x,1,m,y){
if((y=dsu[u][i].find(x))!=x) dsu[u][i-1].merge(x,y),dsu[v][i-1].merge(x,y);
}
}
}
int id[MAXN][MAXN];
// Mark connection block
bool mark[MAXN];
void dfs3(int u){
for(int v:G[u]){
if(v!=fa[u][0]) dfs3(v),mark[u]|=mark[v];
}
}
vector<int> A[MAXN];
struct{ vector<int> U,S; } Q[MAXN];
int main(){
#if defined(_LOCAL_)
freopen("in","r",stdin);
// freopen("out","w",stdout);
#else
freopen("wukong.in","r",stdin);
freopen("wukong.out","w",stdout);
#endif
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>m>>qn;
RNG(_,1,n-1,u,v) cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
RNG(i,1,m){
int k; cin>>k; A[i].resize(k);
for(int& u:A[i]) cin>>u;
}
RNG(i,1,qn){
int k; cin>>k; Q[i].U.resize(k);
for(int& u:Q[i].U) cin>>u;
cin>>k; Q[i].S.resize(k);
for(int& x:Q[i].S) cin>>x;
}
dfs1(1,0);
// Restriction 2
RNG(i,1,qn){
auto& U=Q[i].U;
sort(U.begin(),U.end(),[](int u,int v){ return dfn[u]<dfn[v]; });
RNG(j,1,int(U.size())-1){
int u=U[j-1],v=U[j],w=lca(u,v);
upd(u,dep[u]-dep[w],Q[i].S),upd(v,dep[v]-dep[w],Q[i].S);
}
}
dfs2(1);
RNG(u,2,n){
RNG(i,1,m){
int& x=id[dsu[u][0].find(i)][u];
if(!x) x=++ts.nnd;
id[i][u]=x;
}
}
// Restriction 1
RNG(i,1,m){
fill_n(mark+1,n,0);
auto& S=A[i];
for(int u:S) mark[u]=1;
int r=S[0];
RNG(j,1,int(S.size())-1) r=lca(r,S[j]);
dfs3(r);
if(r!=1) ts.add(var(id[i][r],0),var(id[i][r],1));
RNG(u,2,n){
if(!mark[u]&&mark[fa[u][0]]) ts.add(var(id[i][u],1),var(id[i][u],0));
}
}
// Only 1 output edge
RNG(i,1,m){
RNG(u,1,n){
int lst=0;
for(int v:G[u]){
int x=(v==fa[u][0]?var(id[i][u],0):var(id[i][v],1));
int y=var(++ts.nnd,1);
if(lst) ts.add(lst,y),ts.add(lst,neg(x));
ts.add(x,y);
lst=y;
}
}
}
if(!ts.solve()){ cout<<-1<<"\n"; return 0; }
RNG(i,1,m){
RNG(u,1,n){
bool flag=0;
for(int v:G[u]){
int x=(v==fa[u][0]?var(id[i][u],0):var(id[i][v],1));
flag|=ts.sol[x];
}
if(!flag){ ans[i]=u; continue; }
}
}
RNG(i,1,m) cout<<ans[i]<<" ";
cout<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Dangerous Syscalls
Test #1:
score: 0
Dangerous Syscalls
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:
result:
Subtask #2:
score: 0
Dangerous Syscalls
Test #8:
score: 0
Dangerous Syscalls
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:
result:
Subtask #3:
score: 0
Dangerous Syscalls
Test #19:
score: 0
Dangerous Syscalls
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:
result:
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%