oj.uz

Submission #724957

# Submission time Handle Problem Language Result Execution time Memory
724957 2023-04-16T11:41:25 Z berr Jail (JOI22_jail) C++17
0 / 100
 14 ms 8276 KB 
#include <bits/stdc++.h>
using namespace std; 
const int N = 1e5 + 2e4 + 37;
vector<int> adj[N], adj2[N], s(N), e(N), ti(N), to(N), vis(N);
int par[N][18], cnt, flag;


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 = 17; i >= 0; i--){
        if(!ia(par[x][i], y)){
            x = par[x][i];
            sum += 1<<i;
        }
    }

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


    if(x==y) return sum;

    swap(x, y);

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

    sum++;
    return sum;
}

bool c(int x, int y){//  s1 e2    s2 e2
    return(d(s[x], e[x]) == (d(s[x], e[y])+ d(e[y], e[x])));
    
}

void dfs(int v, int p){
    par[v][0] = p;
    
    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 (i==z-1) flag = 0;
        else if(vis[i]!=z) dfs2(i, z);
    }
}

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);
    }

    dfs(0, 0);

    for (int i = 1; i < 18; 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]--;
    }

    for (int i = 0; i < m; i++){
        for (int l = i+1; l < m; l++){
            if (c(i, l)&&c(l, i)) flag=0;
        }
    }

 /*   for(int i = 0; i < n; i++){
        if(!vis[i]){
            dfs2(i, 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;
    }
}

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 4 ms 8276 KB Output is correct
2 Correct 6 ms 8276 KB Output is correct
3 Correct 6 ms 8276 KB Output is correct
4 Incorrect 14 ms 8276 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 28.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.0

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