제출 #648225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
648225		victor_gao	Jail (JOI22_jail)	C++17	10 / 100	2283 ms	631640 KiB

jail

//#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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23