oj.uz

Submission #648214

# Submission time Handle Problem Language Result Execution time Memory
648214 2022-10-05T17:32:19 Z victor_gao Jail (JOI22_jail) C++17
5 / 100
 2050 ms 632916 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 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){
        if (have1[0][u]&&have2[0][u])
            ng[Hash(u,0,1)].push_back(Hash(u,0,2));
        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;
        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;
        }
        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);
            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 66 ms 130252 KB Output is correct
2 Correct 64 ms 130336 KB Output is correct
3 Correct 67 ms 130312 KB Output is correct
4 Correct 195 ms 130960 KB Output is correct
5 Correct 287 ms 131364 KB Output is correct
6 Correct 81 ms 130900 KB Output is correct
7 Correct 82 ms 130872 KB Output is correct
8 Correct 81 ms 131148 KB Output is correct
9 Correct 640 ms 146340 KB Output is correct
10 Correct 316 ms 232900 KB Output is correct
11 Correct 110 ms 130528 KB Output is correct
12 Correct 330 ms 131748 KB Output is correct
13 Correct 801 ms 364160 KB Output is correct
14 Correct 870 ms 371900 KB Output is correct
15 Correct 1468 ms 481708 KB Output is correct
16 Correct 2050 ms 632916 KB Output is correct
17 Correct 621 ms 304408 KB Output is correct
18 Correct 781 ms 368580 KB Output is correct
19 Correct 641 ms 314872 KB Output is correct
20 Correct 621 ms 314948 KB Output is correct
21 Correct 1376 ms 509664 KB Output is correct
22 Correct 815 ms 369536 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 130276 KB Output is correct
2 Correct 68 ms 130236 KB Output is correct
3 Correct 82 ms 130924 KB Output is correct
4 Correct 80 ms 130876 KB Output is correct
5 Correct 88 ms 130836 KB Output is correct
6 Incorrect 79 ms 130900 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 130276 KB Output is correct
2 Correct 68 ms 130236 KB Output is correct
3 Correct 82 ms 130924 KB Output is correct
4 Correct 80 ms 130876 KB Output is correct
5 Correct 88 ms 130836 KB Output is correct
6 Incorrect 79 ms 130900 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 130276 KB Output is correct
2 Correct 68 ms 130236 KB Output is correct
3 Correct 82 ms 130924 KB Output is correct
4 Correct 80 ms 130876 KB Output is correct
5 Correct 88 ms 130836 KB Output is correct
6 Incorrect 79 ms 130900 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 130276 KB Output is correct
2 Correct 68 ms 130236 KB Output is correct
3 Correct 82 ms 130924 KB Output is correct
4 Correct 80 ms 130876 KB Output is correct
5 Correct 88 ms 130836 KB Output is correct
6 Incorrect 79 ms 130900 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 130280 KB Output is correct
2 Correct 75 ms 130288 KB Output is correct
3 Correct 82 ms 130344 KB Output is correct
4 Correct 69 ms 130208 KB Output is correct
5 Correct 120 ms 130440 KB Output is correct
6 Correct 76 ms 130940 KB Output is correct
7 Incorrect 76 ms 130888 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 130252 KB Output is correct
2 Correct 64 ms 130336 KB Output is correct
3 Correct 67 ms 130312 KB Output is correct
4 Correct 195 ms 130960 KB Output is correct
5 Correct 287 ms 131364 KB Output is correct
6 Correct 81 ms 130900 KB Output is correct
7 Correct 82 ms 130872 KB Output is correct
8 Correct 81 ms 131148 KB Output is correct
9 Correct 640 ms 146340 KB Output is correct
10 Correct 316 ms 232900 KB Output is correct
11 Correct 110 ms 130528 KB Output is correct
12 Correct 330 ms 131748 KB Output is correct
13 Correct 801 ms 364160 KB Output is correct
14 Correct 870 ms 371900 KB Output is correct
15 Correct 1468 ms 481708 KB Output is correct
16 Correct 2050 ms 632916 KB Output is correct
17 Correct 621 ms 304408 KB Output is correct
18 Correct 781 ms 368580 KB Output is correct
19 Correct 641 ms 314872 KB Output is correct
20 Correct 621 ms 314948 KB Output is correct
21 Correct 1376 ms 509664 KB Output is correct
22 Correct 815 ms 369536 KB Output is correct
23 Correct 74 ms 130276 KB Output is correct
24 Correct 68 ms 130236 KB Output is correct
25 Correct 82 ms 130924 KB Output is correct
26 Correct 80 ms 130876 KB Output is correct
27 Correct 88 ms 130836 KB Output is correct
28 Incorrect 79 ms 130900 KB Output isn't correct
29 Halted 0 ms 0 KB -