oj.uz

Submission #648225

# Submission time Handle Problem Language Result Execution time Memory
648225 2022-10-05T17:55:22 Z victor_gao Jail (JOI22_jail) C++17
10 / 100
 2283 ms 631640 KB 
//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define pii pair<int,int>
#define x first
#define y second
#define N 120015
#define C 21*120005
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,m,ac[25][N],have1[25][N],have2[25][N],in[N],out[N],dep[N],t=0,st[N],ed[N];
int after_st[N],after_ed[N];
int dfn[45*N],low[45*N],dft=0;
bool ins[45*N],ans=1;
stack<int>s;
vector<int>g[N],ng[45*N];
void dfs(int p,int lp){
    ac[0][p]=lp;
    in[p]=++t;
    dep[p]=dep[lp]+1;
    for (auto i:g[p]){
        if (i!=lp) dfs(i,p);
    }
    out[p]=++t;
}
int Hash(int u,int p,int i){
    return p*2*n+2*(u-1)+i;
}
void build(){
    out[0]=1e9; in[0]=0;
    for (int i=1;i<=19;i++){
        for (int j=1;j<=n;j++){
            ac[i][j]=ac[i-1][ac[i-1][j]];
            have1[i][j]=have1[i-1][j]+have1[i-1][ac[i-1][j]];
            if (have1[i-1][j]) ng[Hash(j,i-1,1)].push_back(Hash(j,i,1));
            if (have1[i-1][ac[i-1][j]]) ng[Hash(ac[i-1][j],i-1,1)].push_back(Hash(j,i,1));
            have2[i][j]=have2[i-1][j]+have2[i-1][ac[i-1][j]];
            if (have2[i-1][j]) ng[Hash(j,i,2)].push_back(Hash(j,i-1,2));
            if (have2[i-1][ac[i-1][j]]) ng[Hash(j,i,2)].push_back(Hash(ac[i-1][j],i-1,2));
        }
    }
}
bool check(int a,int b){
    return in[a]<=in[b]&&out[a]>=out[b];
}
int LCA(int a,int b){
    if (check(a,b)) return a;
    if (check(b,a)) return b;
    for (int i=19;i>=0;i--){
        if (!check(ac[i][a],b)) a=ac[i][a];
    }
    return ac[0][a];
}
void add(int u,int up,int is){
    if (up<=0){
        return;
    }
    int now=u;
    for (int i=19;i>=0;i--){ // 遇不同
        if (up&(1LL<<i)){
            if (is==1){
                ng[Hash(u,0,1)].push_back(Hash(now,i,2));
               // cout<<"add diff: "<<Hash(u,0,1)<<" "<<Hash(now,i,2)<<" "<<u<<' '<<now<<'\n';
            }
            else {
                ng[Hash(now,i,1)].push_back(Hash(u,0,2));
               // cout<<"add diff: "<<Hash(now,i,1)<<" "<<Hash(u,0,2)<<" "<<now<<" "<<u<<'\n';
            }
            now=ac[i][now];
        }
    }
    now=ac[0][u];
    for (int i=19;i>=0;i--){
        if (up&(1LL<<i)){
            if (is==1){
                ng[Hash(now,i,1)].push_back(Hash(u,0,1));
               // cout<<"add same: "<<Hash(now,i,1)<<" "<<Hash(u,0,1)<<'\n';
            }
            else {
                ng[Hash(u,0,2)].push_back(Hash(now,i,2));
              //  cout<<"add same: "<<Hash(u,0,2)<<" "<<Hash(now,i,2)<<'\n';
            }
            now=ac[i][now];
        }
    }
}
void tarjan(int p){
    dfn[p]=low[p]=++dft;
    s.push(p); ins[p]=1;
    for (auto i:ng[p]){
        if (!dfn[i]){
            tarjan(i);
            low[p]=min(low[p],low[i]);
        }
        else if (ins[i]&&dfn[i]<dfn[p])
            low[p]=min(low[p],dfn[i]);
    }
    if (low[p]==dfn[p]){
        int cnt=0;
        vector<int>cycle;
        for (int x=0;x!=p;s.pop()){
            x=s.top();
            cycle.push_back(x);
            ins[x]=0; cnt++;
        }
        if (cnt>=2){
            ans=0;
            /*
            cout<<"Find : ";
            for (auto j:cycle)
                cout<<j<<" ";
            cout<<'\n';
            */
        } 
    }
}
void reset(){
    t=0; dft=0; ans=1;
    while (!s.empty()) s.pop();
    for (int i=0;i<=n+5;i++){
        g[i].clear();
        st[i]=0; ed[i]=0;
        after_st[i]=0; after_ed[i]=0;
        for (int j=0;j<=20;j++){
            have1[j][i]=0; have2[j][i]=0;
            ac[j][i]=0;
        }
    }
    for (int i=0;i<=42*n;i++){
        ins[i]=0; dfn[i]=0; low[i]=0;
        dep[i]=0; out[i]=0; in[i]=0;
        ng[i].clear();
    }
}
signed main(){
    fast
    int q; cin>>q;
    while (q--){
        cin>>n;
        reset();
        for (int i=1;i<n;i++){
            int a,b; cin>>a>>b;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        cin>>m;
        for (int i=1;i<=m;i++){
            cin>>st[i]>>ed[i];
            have1[0][st[i]]=1;
            have2[0][ed[i]]=1;
            after_st[st[i]]=i;
            after_ed[ed[i]]=i;
        }
        dfs(1,1);
        build();
        /*
        for (int i=0;i<=5*n;i++){
            if (!ng[i].empty()){
                cout<<i<<" -> ";
                for (auto j:ng[i])
                    cout<<j<<" ";
                cout<<'\n';
            }
        }
        */
        for (int i=1;i<=m;i++){
            int a=st[i],b=ed[i];
            int lca=LCA(a,b);
            if (after_ed[lca]&&after_ed[lca]!=i)
                ng[Hash(a,0,1)].push_back(Hash(lca,0,2));
            if (after_st[lca]&&after_st[lca]!=i)
                ng[Hash(lca,0,1)].push_back(Hash(b,0,2));
            int dis=dep[a]-dep[lca];
            add(a,dis,1);
            dis=dep[b]-dep[lca];
            add(b,dis,2);
            ng[Hash(b,0,2)].push_back(Hash(a,0,1));
           // cout<<"add: "<<Hash(b,0,2)<<" "<<Hash(a,0,1)<<'\n';
        }
        /*
        for (int i=0;i<=5*n;i++){
            if (!ng[i].empty()){
                cout<<i<<" -> ";
                for (auto j:ng[i])
                    cout<<j<<" ";
                cout<<'\n';
            }
        }
        */
        for (int i=1;i<42*n;i++){
            if (!dfn[i]) tarjan(i);
        }
        if (ans) cout<<"Yes\n";
        else cout<<"No\n";
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 130252 KB Output is correct
2 Correct 62 ms 130340 KB Output is correct
3 Correct 61 ms 130216 KB Output is correct
4 Correct 175 ms 130916 KB Output is correct
5 Correct 290 ms 131132 KB Output is correct
6 Correct 75 ms 130892 KB Output is correct
7 Correct 76 ms 130892 KB Output is correct
8 Correct 82 ms 131120 KB Output is correct
9 Correct 570 ms 145632 KB Output is correct
10 Correct 329 ms 232840 KB Output is correct
11 Correct 121 ms 130612 KB Output is correct
12 Correct 331 ms 131188 KB Output is correct
13 Correct 855 ms 363604 KB Output is correct
14 Correct 922 ms 371364 KB Output is correct
15 Correct 1596 ms 481168 KB Output is correct
16 Correct 2283 ms 631640 KB Output is correct
17 Correct 685 ms 303860 KB Output is correct
18 Correct 910 ms 367288 KB Output is correct
19 Correct 634 ms 314444 KB Output is correct
20 Correct 640 ms 314488 KB Output is correct
21 Correct 1438 ms 509364 KB Output is correct
22 Correct 868 ms 369136 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 130312 KB Output is correct
2 Correct 72 ms 130256 KB Output is correct
3 Correct 79 ms 130872 KB Output is correct
4 Correct 82 ms 130940 KB Output is correct
5 Correct 91 ms 130892 KB Output is correct
6 Correct 84 ms 130908 KB Output is correct
7 Correct 89 ms 131016 KB Output is correct
8 Correct 82 ms 130868 KB Output is correct
9 Correct 90 ms 130936 KB Output is correct
10 Correct 82 ms 130924 KB Output is correct
11 Correct 80 ms 130824 KB Output is correct
12 Correct 76 ms 130908 KB Output is correct
13 Correct 74 ms 130904 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 130312 KB Output is correct
2 Correct 72 ms 130256 KB Output is correct
3 Correct 79 ms 130872 KB Output is correct
4 Correct 82 ms 130940 KB Output is correct
5 Correct 91 ms 130892 KB Output is correct
6 Correct 84 ms 130908 KB Output is correct
7 Correct 89 ms 131016 KB Output is correct
8 Correct 82 ms 130868 KB Output is correct
9 Correct 90 ms 130936 KB Output is correct
10 Correct 82 ms 130924 KB Output is correct
11 Correct 80 ms 130824 KB Output is correct
12 Correct 76 ms 130908 KB Output is correct
13 Correct 74 ms 130904 KB Output is correct
14 Correct 74 ms 130356 KB Output is correct
15 Correct 80 ms 130344 KB Output is correct
16 Correct 87 ms 131020 KB Output is correct
17 Correct 81 ms 130956 KB Output is correct
18 Correct 82 ms 130928 KB Output is correct
19 Correct 77 ms 130256 KB Output is correct
20 Correct 92 ms 130940 KB Output is correct
21 Correct 87 ms 130836 KB Output is correct
22 Correct 83 ms 130836 KB Output is correct
23 Incorrect 76 ms 130356 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 130312 KB Output is correct
2 Correct 72 ms 130256 KB Output is correct
3 Correct 79 ms 130872 KB Output is correct
4 Correct 82 ms 130940 KB Output is correct
5 Correct 91 ms 130892 KB Output is correct
6 Correct 84 ms 130908 KB Output is correct
7 Correct 89 ms 131016 KB Output is correct
8 Correct 82 ms 130868 KB Output is correct
9 Correct 90 ms 130936 KB Output is correct
10 Correct 82 ms 130924 KB Output is correct
11 Correct 80 ms 130824 KB Output is correct
12 Correct 76 ms 130908 KB Output is correct
13 Correct 74 ms 130904 KB Output is correct
14 Correct 74 ms 130356 KB Output is correct
15 Correct 80 ms 130344 KB Output is correct
16 Correct 87 ms 131020 KB Output is correct
17 Correct 81 ms 130956 KB Output is correct
18 Correct 82 ms 130928 KB Output is correct
19 Correct 77 ms 130256 KB Output is correct
20 Correct 92 ms 130940 KB Output is correct
21 Correct 87 ms 130836 KB Output is correct
22 Correct 83 ms 130836 KB Output is correct
23 Incorrect 76 ms 130356 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 130312 KB Output is correct
2 Correct 72 ms 130256 KB Output is correct
3 Correct 79 ms 130872 KB Output is correct
4 Correct 82 ms 130940 KB Output is correct
5 Correct 91 ms 130892 KB Output is correct
6 Correct 84 ms 130908 KB Output is correct
7 Correct 89 ms 131016 KB Output is correct
8 Correct 82 ms 130868 KB Output is correct
9 Correct 90 ms 130936 KB Output is correct
10 Correct 82 ms 130924 KB Output is correct
11 Correct 80 ms 130824 KB Output is correct
12 Correct 76 ms 130908 KB Output is correct
13 Correct 74 ms 130904 KB Output is correct
14 Correct 74 ms 130356 KB Output is correct
15 Correct 80 ms 130344 KB Output is correct
16 Correct 87 ms 131020 KB Output is correct
17 Correct 81 ms 130956 KB Output is correct
18 Correct 82 ms 130928 KB Output is correct
19 Correct 77 ms 130256 KB Output is correct
20 Correct 92 ms 130940 KB Output is correct
21 Correct 87 ms 130836 KB Output is correct
22 Correct 83 ms 130836 KB Output is correct
23 Incorrect 76 ms 130356 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 130348 KB Output is correct
2 Correct 82 ms 130452 KB Output is correct
3 Correct 70 ms 130272 KB Output is correct
4 Correct 85 ms 130336 KB Output is correct
5 Correct 134 ms 130540 KB Output is correct
6 Correct 81 ms 130948 KB Output is correct
7 Correct 75 ms 130900 KB Output is correct
8 Correct 74 ms 130296 KB Output is correct
9 Incorrect 78 ms 130352 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 130252 KB Output is correct
2 Correct 62 ms 130340 KB Output is correct
3 Correct 61 ms 130216 KB Output is correct
4 Correct 175 ms 130916 KB Output is correct
5 Correct 290 ms 131132 KB Output is correct
6 Correct 75 ms 130892 KB Output is correct
7 Correct 76 ms 130892 KB Output is correct
8 Correct 82 ms 131120 KB Output is correct
9 Correct 570 ms 145632 KB Output is correct
10 Correct 329 ms 232840 KB Output is correct
11 Correct 121 ms 130612 KB Output is correct
12 Correct 331 ms 131188 KB Output is correct
13 Correct 855 ms 363604 KB Output is correct
14 Correct 922 ms 371364 KB Output is correct
15 Correct 1596 ms 481168 KB Output is correct
16 Correct 2283 ms 631640 KB Output is correct
17 Correct 685 ms 303860 KB Output is correct
18 Correct 910 ms 367288 KB Output is correct
19 Correct 634 ms 314444 KB Output is correct
20 Correct 640 ms 314488 KB Output is correct
21 Correct 1438 ms 509364 KB Output is correct
22 Correct 868 ms 369136 KB Output is correct
23 Correct 70 ms 130312 KB Output is correct
24 Correct 72 ms 130256 KB Output is correct
25 Correct 79 ms 130872 KB Output is correct
26 Correct 82 ms 130940 KB Output is correct
27 Correct 91 ms 130892 KB Output is correct
28 Correct 84 ms 130908 KB Output is correct
29 Correct 89 ms 131016 KB Output is correct
30 Correct 82 ms 130868 KB Output is correct
31 Correct 90 ms 130936 KB Output is correct
32 Correct 82 ms 130924 KB Output is correct
33 Correct 80 ms 130824 KB Output is correct
34 Correct 76 ms 130908 KB Output is correct
35 Correct 74 ms 130904 KB Output is correct
36 Correct 74 ms 130356 KB Output is correct
37 Correct 80 ms 130344 KB Output is correct
38 Correct 87 ms 131020 KB Output is correct
39 Correct 81 ms 130956 KB Output is correct
40 Correct 82 ms 130928 KB Output is correct
41 Correct 77 ms 130256 KB Output is correct
42 Correct 92 ms 130940 KB Output is correct
43 Correct 87 ms 130836 KB Output is correct
44 Correct 83 ms 130836 KB Output is correct
45 Incorrect 76 ms 130356 KB Output isn't correct
46 Halted 0 ms 0 KB -