QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#594901 | #7869. 建设终末树 | byron10000 | 15 | 62ms | 100028kb | C++14 | 5.4kb | 2024-09-28 11:05:19 | 2024-09-28 11:05:21 |
Judging History
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";
}
详细
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
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: 15
Accepted
Test #8:
score: 15
Accepted
time: 0ms
memory: 10112kb
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: 2ms
memory: 12136kb
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 3 9 3 8 3 9 3
result:
ok Accepted.
Test #10:
score: 15
Accepted
time: 2ms
memory: 10172kb
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: 0ms
memory: 10108kb
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: 15
Accepted
time: 1ms
memory: 12196kb
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 7 7 7 7 7 7 7 7 7
result:
ok Accepted.
Test #13:
score: 15
Accepted
time: 1ms
memory: 12136kb
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:
4 4 4 4 4 4 4 4 4 4
result:
ok Accepted.
Test #14:
score: 15
Accepted
time: 1ms
memory: 10084kb
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 10 10 10
result:
ok Accepted.
Test #15:
score: 15
Accepted
time: 1ms
memory: 10088kb
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 3 3 3 3 3 5
result:
ok Accepted.
Test #16:
score: 15
Accepted
time: 2ms
memory: 12072kb
input:
10 10 9 2 7 1 8 2 5 9 4 5 3 10 7 4 6 10 8 6 1 2 7 5 4 1 4 10 9 2 1 2 5 10 9 4 2 7 3 1 9 4 2 8 9 4 6 8 3 2 2 8 1 3 2 1 9 4 5 8 9 4 2 9 10 2 1 7 2 10 8 2 7 8 2 3 10 2 7 6 2 8 6 2 5 10 2 6 2 2 5 10 3 5 9 8 2 4 10 2 1 5 2 2 9 2 5 7 3 3 10 1 3 8 4 5 3 5 10 9
output:
-1
result:
ok Accepted.
Test #17:
score: 15
Accepted
time: 0ms
memory: 10076kb
input:
10 10 6 8 10 3 5 4 1 9 6 7 10 7 9 2 8 3 1 4 6 1 1 2 10 9 3 3 6 2 2 8 10 2 10 7 2 8 7 5 9 4 3 10 5 3 8 9 10 1 7 2 2 10 3 4 1 5 3 10 9 5 3 1 9 10 3 6 4 10 5 9 6 1 2 8 4 4 2 5 3 2 4 7 3 9 2 4 3 7 1 3 4 5 8 2 4 4 3 10 1 9 3 10 8 3
output:
1 10 10 10 10 8 10 8 7 8
result:
ok Accepted.
Test #18:
score: 15
Accepted
time: 0ms
memory: 12076kb
input:
10 10 8 3 4 2 8 1 4 1 9 7 5 7 6 5 8 6 10 10 9 2 10 2 3 10 1 2 4 8 5 7 1 2 10 2 1 10 4 1 9 8 5 6 4 8 6 5 2 9 2 1 9 4 7 1 9 2 6 10 2 4 3 9 8 2 9 4 3 1 4 2 2 7 4 3 6 8 7 2 7 8 2 10 7 3 7 3 1 3 2 9 1 3 10 1 3 2 4 1 3 8 5 6 2 4 9 2 8 1 2 9 2 3 3 6 2 3 6 7 8
output:
8 8 8 8 10 9 9 9 8 7
result:
ok Accepted.
Subtask #3:
score: 0
Runtime Error
Test #19:
score: 0
Runtime Error
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
Wrong Answer
Dependency #2:
100%
Accepted
Test #28:
score: 0
Wrong Answer
time: 62ms
memory: 100028kb
input:
499 499 265 20 482 382 88 211 434 122 198 238 180 411 104 462 291 28 215 220 69 192 172 493 52 25 455 162 29 405 278 161 339 316 212 443 257 419 262 411 458 331 93 106 144 422 264 488 248 86 165 62 411 426 236 443 30 140 260 499 37 295 372 315 237 15 67 403 366 467 235 42 262 61 300 312 362 469 202 ...
output:
298 488 28 270 17 17 222 222 81 325 488 488 28 81 28 17 81 28 369 488 369 222 488 17 380 222 250 369 81 250 479 479 250 442 57 488 81 298 17 267 496 17 496 267 422 496 442 222 488 57 81 479 380 488 28 267 81 17 28 17 298 51 479 298 71 71 28 17 28 222 380 74 442 222 488 28 479 488 488 222 28 298 42 2...
result:
wrong answer restrict 76 is not satisfied.
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%