oj.uz

Submission #631970

# Submission time Handle Problem Language Result Execution time Memory
631970 2022-08-19T09:07:33 Z Mahdi Jail (JOI22_jail) C++17
0 / 100
 6 ms 11604 KB 
#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]]=0;
        for(int u: h[nd[i]]){
            if(!mk[u]){
                cout<<"NO\n";
                return;
            }
        }
        mk[nd[i]]=1;
    }
    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.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11604 KB Output isn't correct
2 Halted 0 ms 0 KB -