Submission #1233639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233639		minhpk	Jail (JOI22_jail)	C++20	0 / 100	21 ms	39496 KiB

jail

#include <bits/stdc++.h>
#define int long long
using namespace std;

// Tối đa N = 1e6, Euler tour dài ~2N
static vector<int> z[1000005];
static int sta[1000005], fin[1000005], high_[1000005];
static int euler[2000005];
static int logarit[2000005];
static int st[2000005][22];     // mở rộng đủ (2*N) × log2(2*N)
static pair<int,int> v[1000005];

int tour;

void dfs(int u, int p){
    sta[u] = ++tour;
    euler[tour] = u;
    for(int w: z[u]){
        if(w == p) continue;
        high_[w] = high_[u] + 1;
        dfs(w, u);
        euler[++tour] = u;
    }
    fin[u] = ++tour;
    euler[tour] = u;
}

void build_st(){
    int N = tour;
    for(int i = 1; i <= N; i++){
        st[i][0] = euler[i];
    }
    int LOG = logarit[N] + 1;
    for(int j = 1; j <= LOG; j++){
        for(int i = 1; i + (1<<j) - 1 <= N; i++){
            int l = st[i][j-1];
            int r = st[i + (1<<(j-1))][j-1];
            st[i][j] = (high_[l] < high_[r] ? l : r);
        }
    }
}

int lca(int x, int y){
    int L = min(sta[x], sta[y]);
    int R = max(sta[x], sta[y]);
    int j = logarit[R - L + 1];
    int a = st[L][j];
    int b = st[R - (1<<j) + 1][j];
    return (high_[a] < high_[b] ? a : b);
}

bool isAnc(int x, int y){
    // y là ancestor của x nếu sta[y] ≤ sta[x] ≤ fin[y]
    return sta[y] <= sta[x] && fin[y] >= sta[x];
}

bool onPath(int x, int y, int u){
    int L = lca(x, y);
    // u nằm trên đường x->y nếu u liên tổ tiên tới L và tổ tiên tới x hoặc y
    return (isAnc(u, x) && isAnc(L, u)) || (isAnc(u, y) && isAnc(L, u));
}

void solve(){
    int n; 
    cin >> n;
    // clear cây
    for(int i = 1; i <= n; i++){
        z[i].clear();
        sta[i] = fin[i] = high_[i] = 0;
    }
    tour = 0;
    // đọc cạnh
    for(int i = 1; i < n; i++){
        int u, v; 
        cin >> u >> v;
        z[u].push_back(v);
        z[v].push_back(u);
    }
    // build Euler + RMQ
    dfs(1, 0);
    build_st();

    int m; 
    cin >> m;
    for(int i = 1; i <= m; i++){
        cin >> v[i].first >> v[i].second;
    }

    bool ok = true;
    for(int i = 1; i <= m && ok; i++){
        for(int j = i+1; j <= m; j++){
            int x = v[i].first, y = v[i].second;
            int u = v[j].first, w = v[j].second;
            // cả x,y nằm trên đường u->w?
            if(onPath(u, w, x) && onPath(u, w, y)){
                ok = false;
                break;
            }
            // cả u,w nằm trên đường x->y?
            if(onPath(x, y, u) && onPath(x, y, w)){
                ok = false;
                break;
            }
        }
    }

    cout << (ok ? "Yes\n" : "No\n");
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // build logarit up to max Euler length = 2*1e6
    logarit[1] = 0;
    for(int i = 2; i < 2000005; i++){
        logarit[i] = logarit[i/2] + 1;
    }

    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