Submission #724990

#	Time	Username	Problem	Language	Result	Execution time	Memory
724990		berr	Jail (JOI22_jail)	C++17	49 / 100	5082 ms	31176 KiB

jail

#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);
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
    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(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;
    
    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 dfs3(int v, int z){
    vis[v] = z;

    for (auto i: adj3[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)) adj2[i].push_back(l);

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

            if(c2(i, l)) flag = 0;
            if(c2(l, i)) flag = 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;
    }
}

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

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

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23