Submission #1168595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168595		sitablechair	Jail (JOI22_jail)	C++20	100 / 100	1509 ms	355328 KiB

jail

#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);

#ifdef NCGM
#include"debug.h"
#else 
#define debug(...) "fr";
#endif

using namespace std;

const int N=120004;

int n,m,par[20][N],d[N],vs[N*50],st[N];
bool check=0;
vector<int> g[N],g1[N*50];
pair<int,int> pp[N];
void dfs(int u,int p=0) {
    for(auto v: g[u]) 
        if (v!=p) {
            d[v]=d[u]+1;
            par[0][v]=u;
            g1[u].pb(v+n);
            g1[v].pb(v+n);
            if (st[u]) g1[v+n*18].pb(st[u]);
            if (st[v]) g1[v+n*18].pb(st[v]);
            For(i,1,16) {
                if (par[i-1][par[i-1][v]]==0) break;
                par[i][v]=par[i-1][par[i-1][v]];
                g1[v+n*i].pb(v+n*(i+1));
                g1[i*n+par[i-1][v]].pb(v+n*(i+1));
            }
            For(i,1,16) {
                if (par[i-1][par[i-1][v]]==0) break;
                g1[v+n*(i+18)].pb(v+n*(i+17));
                g1[v+n*(i+18)].pb(n*(i+17)+(par[i-1][v]));
            }
            dfs(v,u);
        }
}
int lca(int u,int v) {
    if (d[v]>d[u]) swap(u,v);
    int dd=d[u]-d[v];
    For(i,0,16)
        if (dd>>i&1) u=par[i][u];
    if (u==v) return u;
    ForD(i,16,0)
        if (par[i][u]!=par[i][v]) u=par[i][u],v=par[i][v];
    return par[0][u];
    
}
void add_path(int x,int u,int v,bool bodi=0) {
    if (d[v]>d[u]) swap(u,v);
    if (bodi && u==v) return;
    if (u==v || (par[0][u]==v && bodi)) {
        g1[u].pb(x);
        return;
    }
    int dd=d[u]-d[v]-bodi;
    For(i,0,16)
        if (dd>>i&1) {
            g1[u+n*(i+1)].pb(x);
            u=par[i][u];
        }
}
void add_path1(int x,int u,int v,bool bodi=0) {
    if (d[v]>d[u]) swap(u,v);
    if (bodi && u==v) return;
    if (u==v || (par[0][u]==v && bodi)) {
        if (st[u]) g1[x].pb(st[u]);
        return;
    }
    int dd=d[u]-d[v]-bodi;
    For(i,0,16)
        if (dd>>i&1) {
            g1[x].pb(u+n*(i+18));
            u=par[i][u];
        }
}
void dfs1(int u) {
    vs[u]=1;
    for(auto v: g1[u])
        if (vs[v]==0) {
            dfs1(v);
        } else if (vs[v]==1 && v!=u) {
            check=0;
            return;
        }
    vs[u]=2;
}
void solve() {
    cin >> n;
    fill(st,st+1+n,0);
    For(j,0,16)
        For(i,1,n) par[j][i]=0;
    For(i,1,n)
        For(j,0,33) vs[i+n*j]=0;
    For(i,1,n-1) {
        int u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    cin >> m;
    For(i,1,m) {
        cin >> pp[i].ff >> pp[i].ss;
        st[pp[i].ss]=pp[i].ff;
    }
    dfs(1);

    For(i,1,m) {
        int s=pp[i].ff,t=pp[i].ss;
        if (s==t) continue;
        if (lca(s,t)==t) {
            add_path(s,par[0][s],t);
            add_path1(s,s,t,1);
        } else if (lca(s,t)==s) {
            add_path(s,t,s,1);
            add_path1(s,par[0][t],s);
        } else {  
            add_path(s,par[0][s],lca(s,t));
            add_path1(s,par[0][t],lca(s,t));
            add_path(s,t,lca(s,t));
            add_path1(s,s,lca(s,t));
        }
    }
    check=1;
    For(i,1,n)
        For(j,0,33)
            if (!vs[i+n*j]) dfs1(i+n*j);
    if (check) cout << "Yes\n";
    else cout << "No\n";
    For(i,1,n) g[i].clear();
    For(i,1,n)
        For(j,0,33) g1[i+n*j].clear();
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t=1;
    cin >> t;
    while(t--) solve();
    return 0;
}

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