Submission #1233691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233691		minhpk	Jail (JOI22_jail)	C++20	0 / 100	26 ms	55208 KiB

jail

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

vector<int> z[1000005];
vector<int> z1[1000005];
int sta[1000005], fin[1000005], tour;
int euler[2000005], high[1000005];
int logarit[1000005], st[400001][21];
pair<int,int> v[1000005];
int up[1000005];
int cnt[1000005], cnt1[1000005];
int pos[1000005];
bool vis[1000005];

void dfs(int i, int par) {
    up[i] = par;
    tour++;
    sta[i] = tour;
    euler[tour] = i;
    for (auto p : z[i]) {
        if (p == par) continue;
        high[p] = high[i] + 1;
        dfs(p, i);
        tour++;
        euler[tour] = i;
    }
    tour++;
    fin[i] = tour;
    euler[tour] = i;
}

void buildst() {
    for (int i = 1; i <= tour; i++)
        st[i][0] = euler[i];
    for (int j = 1; j <= 20; j++) {
        for (int i = 1; i + (1 << j) - 1 <= tour; 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 idx1 = st[l][j];
    int idx2 = st[r - (1 << j) + 1][j];
    return (high[idx1] < high[idx2] ? idx1 : idx2);
}

bool isanc(int x, int y) {
    return sta[x] >= sta[y] && fin[x] <= fin[y];
}

bool onpath(int x, int y, int u) {
    int l = lca(x, y);
    return ((isanc(x, u) && isanc(u, l)) || (isanc(y, u) && isanc(u, l)));
}

int calc(int x, int y) {
    return high[x] + high[y] - 2 * high[lca(x, y)];
}

int duongkinh(int a) {
    int pos = 1, dis = 0;
    for (int i = 1; i <= a; i++) {
        int d = calc(1, i);
        if (d > dis) { dis = d; pos = i; }
    }
    int pos1 = pos, dis1 = 0;
    for (int i = 1; i <= a; i++) {
        int d = calc(pos, i);
        if (d > dis1) { dis1 = d; pos1 = i; }
    }
    return calc(pos, pos1);
}

void dfs1(int i, stack<int>& s) {
    vis[i] = true;
    for (auto p : z1[i]) {
        if (!vis[p]) dfs1(p, s);
    }
    s.push(i);
}

void solve() {
    int a;
    cin >> a;
    for (int i = 1; i < a; i++) {
        int x, y;
        cin >> x >> y;
        z[x].push_back(y);
        z[y].push_back(x);
    }
    tour = 0;
    dfs(1, 0);
    buildst();
    int diameter = duongkinh(a);

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

    if (diameter > 50) {
        for (int i = 1; i <= c; i++) {
            auto [x,y] = v[i];
            for (int j = 1; j <= c; j++) {
                if (i == j) continue;
                auto [u,v1] = v[j];
                if (onpath(x,y,u))   z1[j].push_back(i);
                if (onpath(x,y,v1))  z1[i].push_back(j);
            }
        }
    } else {
        for (int i = 1; i <= c; i++) {
            auto [x,y] = v[i];
            int l = lca(x, y);
            int p1 = up[x];
            if (x!=l){
            while (p1 != l) {
                if (cnt[p1])   z1[cnt[p1]].push_back(i);
                if (cnt1[p1])  z1[i].push_back(cnt1[p1]);
                p1 = up[p1];
            }
            }
            p1 = up[y];
           if (y!=l){
            while (p1 != l) {
                if (cnt[p1])   z1[cnt[p1]].push_back(i);
                if (cnt1[p1])  z1[i].push_back(cnt1[p1]);
                p1 = up[p1];
            }
           }
        }
    }

    stack<int> s;
    for (int i = 1; i <= c; i++) {
        if (!vis[i]) dfs1(i, s);
    }
    vector<int> order;
    while (!s.empty()) {
        order.push_back(s.top());
        s.pop();
    }
    for (int i = 0; i < (int)order.size(); i++) pos[order[i]] = i;

    bool ok = true;
    for (int u = 1; u <= c && ok; u++) {
        for (int v : z1[u]) {
            if (pos[u] > pos[v]) { ok = false; break; }
        }
    }
    cout << (ok ? "Yes\n" : "No\n");

    for (int i = 1; i <= max(a, c); i++) {
        z[i].clear();
        z1[i].clear();
        vis[i] = false;
        pos[i] = 0;
        cnt[i] = cnt1[i] = 0;
    }
    for (int i = 1; i <= a; i++) {
        for (int j = 0; j <= 20; j++) st[i][j] = 0;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    logarit[2] = 1;
    for (int i = 3; i <= 1000000; i++) logarit[i] = logarit[i/2] + 1;
    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