Submission #632609

#	Time	Username	Problem	Language	Result	Execution time	Memory
632609		Mahdi	Jail (JOI22_jail)	C++17	49 / 100	254 ms	87228 KiB

jail

    #include<bits/stdc++.h>
    #pragma GCC optimize("Ofast")
    using namespace std;
    #define all(v) v.begin(), v.end()
    #define F first
    #define S second
    typedef pair<int, int> pii;
    typedef long long ll;
    const int N=12e4+5;
    int n, m, nm, sq, s[N], t[N], dis[N], pr[N][18];
    vector<int>g[N], h[3*N], nd;
    bool mk[3*N];
    pii st[N];
     
    void dfs(const int &v, const int &p=-1){
        for(int u: g[v]){
            if(u!=p){
                pr[u][0]=v;
                for(int i=1;i<17;++i)
                    pr[u][i]=pr[pr[u][i-1]][i-1];
                dis[u]=dis[v]+1;
                dfs(u, v);
            }   
        }
    }
     
    int par(int v, int p){
        for(int i=0;p>0;++i){
            if(p&1)
                v=pr[v][i];
            p>>=1;
        }
        return v;
    }
     
    int lca(int u, int v){
        u=par(u, dis[u]-dis[v]);
        v=par(v, dis[v]-dis[u]);
        if(u==v)
            return v;
        for(int i=16;i>=0;--i){
            if(pr[u][i]!=pr[v][i]){
                v=pr[v][i];
                u=pr[u][i];
            }
        }
        return pr[v][0];
    }
     
    void pre(){
        nm=2*n+m;
        for(int i=0;i<nm;++i)
            h[i].clear();
        for(int v=0;v<n;++v){
            int u=v, w=par(v, sq);
            while(u!=w){
                if(s[u]!=-1)
                    h[s[u]+2*n].push_back(v);
                if(t[u]!=-1)
                    h[v+n].push_back(t[u]+2*n);
                u=pr[u][0];
            }
        }
    }
     
    void opr(int i, int v, int u){
        int w=lca(u, v);
        int x=pr[v][0];
        int y=par(x, sq);
        while(dis[y]>=dis[w]){
            h[x].push_back(i);
            x=y;
            y=par(x, sq);
            if(x==w)
                break;
        }
        for(;dis[x]>=dis[w];x=pr[x][0]){
            if(s[x]!=-1)
                h[s[x]+2*n].push_back(i);
            if(x==w)
                break;
        }
        x=v;
        y=par(v, sq);
        while(dis[y]>=dis[w]){
            h[i].push_back(x+n);
            x=y;
            y=par(x, sq);
            if(x==w)
                break;
        }
        for(;dis[x]>=dis[w];x=pr[x][0]){
            if(t[x]!=-1)
                h[i].push_back(t[x]+2*n);
            if(x==w)
                break;
        }
        x=pr[u][0];
        y=par(x, sq);
        while(dis[y]>=dis[w]){
            h[i].push_back(x+n);
            x=y;
            y=par(x, sq);
            if(x==w)
                break;
        }
        for(;dis[x]>dis[w];x=pr[x][0]){
            if(t[x]!=-1)
                h[i].push_back(t[x]+2*n);
        }
        x=u;
        y=par(x, sq);
        while(dis[y]>=dis[w]){
            h[x].push_back(i);
            x=y;
            y=par(x, sq);
            if(x==w)
                break;
        }
        for(;dis[x]>dis[w];x=pr[x][0]){
            if(s[x]!=-1)
                h[s[x]+2*n].push_back(i);
        }
    }
     
    void sfd(const int &v){
        mk[v]=1;
        for(int u: h[v]){
            if(!mk[u])
                sfd(u);
        }
        nd.push_back(v);
    }
     
    void sol(){
        cin>>n;
        sq=sqrt(n);
        for(int i=0;i<n;++i)
            g[i].clear();
        for(int i=1;i<n;++i){
            int u, v;
            cin>>u>>v;
            g[--v].push_back(--u);
            g[u].push_back(v);
        }
        cin>>m;
        memset(s, -1, 4*n);
        memset(t, -1, 4*n);
        for(int i=0;i<m;++i){
            int u, v;
            cin>>u>>v;
            s[--u]=i;
            t[--v]=i;
            st[i]={u, v};
        }
        dfs(0);
        pre();    
        for(int i=0;i<m;++i)
            opr(2*n+i, st[i].F, st[i].S);
        nd.clear();
        memset(mk, 0, 4*nm);
        for(int i=0;i<nm;++i){
            if(!mk[i])
                sfd(i);
        }
        memset(mk, 0, 4*nm);
        for(int i=0;i<nm;++i){
            mk[nd[i]]=1;
            for(int u: h[nd[i]]){
                if(!mk[u]){
                    cout<<"No\n";
                    return;
                }
            }
        }
        cout<<"Yes\n";
    }
     
    int main(){
        ios_base::sync_with_stdio(0); cin.tie(0);
        int T;
        cin>>T;
        while(T--)
            sol();
    }

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23