oj.uz

Submission #725023

# Submission time Handle Problem Language Result Execution time Memory
725023 2023-04-16T13:07:53 Z berr Jail (JOI22_jail) C++17
0 / 100
 21 ms 12520 KB 
#include <bits/stdc++.h>
using namespace std; 
const int N = 1e5 + 2e4 + 37;
vector<int> adj[N], adj2[N], adj3[N], s(N), e(N), ti(N), to(N), vis(N), de(N), qe(N, -1), qs(N, -1);
int par[N][18], cnt, flag, taa=0;


bool ia(int x, int y){
    return ti[x] <= ti[y] && to[x] >= to[y];
}

int d(int x, int y){


    if(x == y) return 0;

    int sum = 0;

    if(ia(x, y)) swap(x, y);

    for (int i = 5; i >= 0; i--){
        if(!ia(par[x][i], y)){
            x = par[x][i];
            sum += 1<<i;
        }
    }   
    

    sum++;
    x=par[x][0];



    swap(x, y);

    sum+=de[x]-de[y];
    return sum;
}

bool c(int x, int y){
    if(x==y || x==-1 || y==-1) return 0;

    if( (d(s[x], e[x]) == (d(s[x], e[y])+ d(e[y], e[x])))) return 1;
    swap(x, y);
    return (d(s[x], e[x]) == (d(s[x], s[y])+ d(s[y], e[x])));
}
bool c2(int x, int y){
    if(x==y || x==-1 || y==-1 ) return 0;

    if(d(s[x], e[x]) == d(s[x], s[y])+ d(s[y], e[y]) + d(e[y], e[x])) return 1;
    if(d(s[x], e[x]) == d(s[x], e[y])+ d(e[y], s[y]) + d(s[y], e[x])) return 1;
    return 0;
}

void dfs(int v, int p){
    par[v][0] = p;
    de[v]=de[p]+1;
    ti[v] = cnt++;
    
    for (auto i: adj[v]){
        if (i == p) continue;
        dfs(i, v);
    }

    to[v] = cnt++;
}

void dfs2(int v, int z){
    vis[v] = z;

    for (auto i: adj2[v]){
        if (vis[i]==z) flag = 0;
        else if(vis[i]<z) dfs2(i, z);
    }

    vis[v]=z+1;
}

void solve(){
    int n; cin >> n;
    cnt = 0;

    for (int i = 1; i < n; i++){
        int x, y; cin >> x >> y;
        x--; y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    de[0]=-1;
    dfs(0, 0);

    for (int i = 1; i < 6; i++){
        for(int l = 0; l < n; l++){
            par[l][i] = par[par[l][i-1]][i-1];
        }
    }

    flag = 1;

    int m; cin >> m;

    for (int i = 0; i < m; i++){
        cin >> s[i] >> e[i];
        s[i]--; e[i]--;
        qs[s[i]]=i;
        qe[e[i]]=i;
 
    }

  for(int i=0;i<m; i++){

        int x=s[i], y=e[i];


        while(!ia(x, y)){

            int l=qs[x];
            if (c(i, l)) adj2[i].push_back(l);


            if(c2(i, l)) flag = 0;

            l=qe[x];
            if (c(i, l)) adj2[i].push_back(l);


            if(c2(i, l)) flag = 0;

            x=par[x][0];
        }

        int l=qs[x];
        if (c(i, l)) adj2[i].push_back(l);


            if(c2(i, l)) flag = 0;
                    l=qe[x];

                 if (c(i, l)) adj2[i].push_back(l);

                    
            if(c2(i, l)) flag = 0;

         while(!ia(y, x)){
            int l=qs[y];

            if (c(i, l)) adj2[i].push_back(l);


            if(c2(i, l)) flag = 0;

            l=qe[y];
                   if (c(i, l)) adj2[i].push_back(l);


            if(c2(i, l)) flag = 0;

            y=par[y][0];
        }


    }


    for(int i = 0; i < n; i++){
        if(vis[i]==0) dfs2(i, n*i+1);
    }


    if(flag) cout<<"Yes\n";
    else cout<<"No\n";

    for (int i = 0; i < n; i++){
        adj[i].clear();
        adj2[i].clear();
        vis[i] = 0;
        qs[i]=qe[i]=-1;
    }




}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
        
    int t; cin>>t;

    while(t--){
        solve();
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12500 KB Output is correct
2 Correct 6 ms 12500 KB Output is correct
3 Correct 8 ms 12500 KB Output is correct
4 Incorrect 15 ms 12508 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12500 KB Output is correct
2 Correct 7 ms 12500 KB Output is correct
3 Incorrect 7 ms 12500 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12500 KB Output is correct
2 Correct 7 ms 12500 KB Output is correct
3 Incorrect 7 ms 12500 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12500 KB Output is correct
2 Correct 7 ms 12500 KB Output is correct
3 Incorrect 7 ms 12500 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12500 KB Output is correct
2 Correct 7 ms 12500 KB Output is correct
3 Incorrect 7 ms 12500 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12500 KB Output is correct
2 Correct 7 ms 12500 KB Output is correct
3 Correct 6 ms 12500 KB Output is correct
4 Correct 7 ms 12500 KB Output is correct
5 Correct 21 ms 12500 KB Output is correct
6 Correct 7 ms 12500 KB Output is correct
7 Correct 10 ms 12520 KB Output is correct
8 Correct 6 ms 12500 KB Output is correct
9 Correct 7 ms 12500 KB Output is correct
10 Incorrect 6 ms 12500 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12500 KB Output is correct
2 Correct 6 ms 12500 KB Output is correct
3 Correct 8 ms 12500 KB Output is correct
4 Incorrect 15 ms 12508 KB Output isn't correct
5 Halted 0 ms 0 KB -