Submission #1233618

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233618		minhpk	Jail (JOI22_jail)	C++20	0 / 100	11 ms	23876 KiB

jail

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 1000005;
vector<int> g[MAXN];
int par[MAXN], depth[MAXN];
int sta[MAXN], fin[MAXN], tour;
int euler[3*MAXN], log2_[3*MAXN], st[3*MAXN][20], N;
int S1, T1, S2, T2;

void dfs(int u, int p){
    par[u] = p;
    depth[u] = (p == 0 ? 0 : depth[p] + 1);
    sta[u] = ++tour; euler[tour] = u;
    for(int v : g[u]){
        if(v == p) continue;
        dfs(v, u);
        euler[++tour] = u;
    }
    fin[u] = ++tour; euler[tour] = u;
}

void build_lca(){
    for(int i = 1; i <= tour; i++)
        st[i][0] = euler[i];
    for(int j = 1; (1<<j) <= tour; j++){
        for(int i = 1; i + (1<<j) - 1 <= tour; i++){
            int x = st[i][j-1];
            int y = st[i + (1<<(j-1))][j-1];
            st[i][j] = (depth[x] < depth[y] ? x : y);
        }
    }
    log2_[1] = 0;
    for(int i = 2; i <= tour; i++)
        log2_[i] = log2_[i/2] + 1;
}

int lca(int u, int v){
    int L = min(sta[u], sta[v]);
    int R = max(sta[u], sta[v]);
    int j = log2_[R - L + 1];
    int x = st[L][j];
    int y = st[R - (1<<j) + 1][j];
    return depth[x] < depth[y] ? x : y;
}

vector<int> get_path(int u, int v){
    int w = lca(u, v);
    vector<int> pu, pv;
    int x = u;
    while(x != w){
        pu.push_back(x);
        x = par[x];
    }
    pu.push_back(w);
    x = v;
    while(x != w){
        pv.push_back(x);
        x = par[x];
    }
    reverse(pv.begin(), pv.end());
    pu.insert(pu.end(), pv.begin(), pv.end());
    return pu;
}

void solve(){
    cin >> N;
    for(int i = 1; i <= N; i++) g[i].clear();
    for(int i = 1, u, v; i < N; i++){
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    tour = 0;
    dfs(1, 0);
    build_lca();

    int M;
    cin >> M;
    cin >> S1 >> T1 >> S2 >> T2;
    vector<char> mark(N+1, 0);
    auto p1 = get_path(S1, T1);
    for(int u : p1) mark[u] = 1;

    auto p2 = get_path(S2, T2);
    for(int u : p2){
        if(mark[u]){
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}

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