oj.uz

Submission #632667

# Submission time Handle Problem Language Result Execution time Memory
632667 2022-08-20T14:24:22 Z Mahdi Jail (JOI22_jail) C++17
0 / 100
 2640 ms 1048576 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);
        }   
    }
}
     
inline int par(int v, int p){
    if(p>0)
        return max(0, v-p);
    return v;
    for(int i=0;p>0;++i){
        if(p&1)
            v=pr[v][i];
        p>>=1;
    }
    return v;
}
     
inline 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];
        }
    }
}
     
inline 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=2*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, nm);
    for(int i=0;i<nm;++i){
        if(!mk[i])
            sfd(i);
    }
    memset(mk, 0, 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.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11604 KB Output is correct
2 Correct 6 ms 11604 KB Output is correct
3 Correct 6 ms 11604 KB Output is correct
4 Correct 20 ms 11604 KB Output is correct
5 Correct 35 ms 11620 KB Output is correct
6 Correct 7 ms 11604 KB Output is correct
7 Correct 8 ms 11604 KB Output is correct
8 Correct 9 ms 11732 KB Output is correct
9 Correct 122 ms 15580 KB Output is correct
10 Correct 332 ms 44520 KB Output is correct
11 Correct 12 ms 11604 KB Output is correct
12 Correct 59 ms 11672 KB Output is correct
13 Correct 1155 ms 481564 KB Output is correct
14 Correct 1089 ms 490388 KB Output is correct
15 Correct 2640 ms 673556 KB Output is correct
16 Runtime error 2450 ms 1048576 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11628 KB Output is correct
2 Correct 5 ms 11604 KB Output is correct
3 Correct 8 ms 11604 KB Output is correct
4 Runtime error 2443 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11628 KB Output is correct
2 Correct 5 ms 11604 KB Output is correct
3 Correct 8 ms 11604 KB Output is correct
4 Runtime error 2443 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11628 KB Output is correct
2 Correct 5 ms 11604 KB Output is correct
3 Correct 8 ms 11604 KB Output is correct
4 Runtime error 2443 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11628 KB Output is correct
2 Correct 5 ms 11604 KB Output is correct
3 Correct 8 ms 11604 KB Output is correct
4 Runtime error 2443 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11648 KB Output is correct
2 Correct 7 ms 11604 KB Output is correct
3 Correct 7 ms 11604 KB Output is correct
4 Correct 6 ms 11604 KB Output is correct
5 Correct 15 ms 11636 KB Output is correct
6 Runtime error 2458 ms 1048576 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11604 KB Output is correct
2 Correct 6 ms 11604 KB Output is correct
3 Correct 6 ms 11604 KB Output is correct
4 Correct 20 ms 11604 KB Output is correct
5 Correct 35 ms 11620 KB Output is correct
6 Correct 7 ms 11604 KB Output is correct
7 Correct 8 ms 11604 KB Output is correct
8 Correct 9 ms 11732 KB Output is correct
9 Correct 122 ms 15580 KB Output is correct
10 Correct 332 ms 44520 KB Output is correct
11 Correct 12 ms 11604 KB Output is correct
12 Correct 59 ms 11672 KB Output is correct
13 Correct 1155 ms 481564 KB Output is correct
14 Correct 1089 ms 490388 KB Output is correct
15 Correct 2640 ms 673556 KB Output is correct
16 Runtime error 2450 ms 1048576 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -