QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#594901#7869. 建设终末树byron1000015 62ms100028kbC++145.4kb2024-09-28 11:05:192024-09-28 11:05:21

Judging History

你现在查看的是最新测评结果

  • [2024-09-28 11:05:21]
  • 评测
  • 测评结果:15
  • 用时:62ms
  • 内存:100028kb
  • [2024-09-28 11:05:19]
  • 提交

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%