제출 #1168579

#제출 시각아이디문제언어결과실행 시간메모리
1168579sitablechairJail (JOI22_jail)C++20
0 / 100
23 ms17220 KiB
#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=12004;

int n,m,par[20][N],d[N],vs[N],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*17].pb(st[u]);
            if (st[v]) g1[v+n*17].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+17)].pb(v+n*(i+16));
                g1[v+n*(i+17)].pb(n*(i+16)+(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];
    // debug(u,v,par[0][4]);
    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);
        // debug(u,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+17));
            u=par[i][u];
        }
}
void dfs1(int u) {
    vs[u]=1;
    for(auto v: g1[u])
        if (vs[v]==0) {
            // if (v==144) debug(u);
            dfs1(v);
        } else if (vs[v]==1 && v!=u) {
            check=0;
            // debug(u,v);
            return;
        }
    vs[u]=2;
}
void solve() {
    cin >> n;
    fill(st,st+1+n,0);
    For(i,1,n)
        For(j,-1,33) vs[i*(j+2)]=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;
        // debug(s,t,lca(s,t));
        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);
            // debug(s,s,t);
        } 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,-1,33)
            if (!vs[i*(j+2)]) dfs1(i*(j+2));
    if (check) cout << "Yes\n";
    else cout << "No\n";
    For(i,1,n) g[i].clear();
    For(i,1,n)
        For(j,-1,33) g1[i*(j+2)].clear();
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t=1;
    cin >> t;
    while(t--) solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...