Submission #1255350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255350		MisterReaper	Jail (JOI22_jail)	C++20	5 / 100	731 ms	413028 KiB

jail

// File V.cpp created on 09.08.2025 at 01:10:05
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

void solve() {
    int N;
    std::cin >> N;

    std::vector<std::vector<int>> adj(N);
    for (int i = 1; i < N; ++i) {
        int A, B;
        std::cin >> A >> B;
        --A, --B;
        adj[A].emplace_back(B);
        adj[B].emplace_back(A);
    }

    int M;
    std::cin >> M;

    std::vector<int> S(M), T(M), ids(N, -1), idt(N, -1);
    for (int i = 0; i < M; ++i) {
        std::cin >> S[i] >> T[i];
        --S[i], --T[i];
        ids[S[i]] = i;
        idt[T[i]] = i;
    }

    const int LG = std::__lg(N) + 1;

    std::vector<int> dep(N);
    std::vector par(LG, std::vector<int>(N, -1));
    auto dfs = [&](auto&& self, int v) -> void {
        for (auto u : adj[v]) {
            par[0][u] = v;
            dep[u] = dep[v] + 1;
            adj[u].erase(std::find(adj[u].begin(), adj[u].end(), v));
            self(self, u);
        }
    };
    dfs(dfs, 0);

    debug(par[0]);

    auto lca = [&](int u, int v) -> int {
        if (dep[u] < dep[v]) {
            std::swap(u, v);
        }
        int d = dep[u] - dep[v];
        for (int i = 0; i < LG; ++i) {
            if (d >> i & 1) {
                u = par[i][u];
            }
        }
        if (u == v) {
            return u;
        }
        for (int i = 0; i < LG; ++i) {
            if (par[i][u] != par[i][v]) {
                u = par[i][u];
                v = par[i][v];
            }
        }
        assert(par[0][u] == par[0][v]);
        return par[0][u];
    };

    const int max_node = N * LG * 4 + 5;

    int node_alloc = N;

    std::vector<std::vector<int>> bdj(N + max_node);

    auto add_edge = [&](int u, int v) {
        if (u != -1 && v != -1) {
            debug(u, v);
            bdj[u].emplace_back(v);
        }
    };

    std::vector up(LG, std::vector<int>(N));
    std::vector dw(LG, std::vector<int>(N));
    for (int i = 0; i < N; ++i) {
        up[0][i] = idt[i];
        dw[0][i] = ids[i];
    }

    debug(90);

    for (int lg = 0; lg + 1 < LG; ++lg) {
        for (int i = 0; i < N; ++i) {
            if (par[lg][i] != -1 && par[lg][par[lg][i]] != -1) {
                par[lg + 1][i] = par[lg][par[lg][i]];
                up[lg + 1][i] = node_alloc++;
                dw[lg + 1][i] = node_alloc++;
                add_edge(up[lg][i], up[lg + 1][i]);
                add_edge(up[lg][par[lg][i]], up[lg + 1][i]);
                add_edge(dw[lg + 1][i], dw[lg][i]);
                add_edge(dw[lg + 1][i], dw[lg][par[lg][i]]);
            }
        }
    }

    debug(104);

    for (int i = 0; i < M; ++i) {
        int s = S[i], t = T[i];

        int l = lca(s, t);
        int ds = dep[s] - dep[l] - 1;
        int dt = dep[t] - dep[l];

        debug(s, t, l, ds, dt);

        if (ds >= 0) {
            s = par[0][s];
            for (int j = 0; j < LG; ++j) {
                if (ds >> j & 1) {
                    add_edge(i, dw[j][s]);
                    s = par[j][s];
                }
            }
            s = S[i];
        }

        if (dt >= 0) {
            for (int j = 0; j < LG; ++j) {
                if (dt >> j & 1) {
                    add_edge(i, dw[j][t]);
                    t = par[j][t];
                }
            }
            t = T[i];
        }

        if (l != s) {
            add_edge(i, ids[l]);
        }

        ds = dep[s] - dep[l];
        dt = dep[t] - dep[l] - 1;

        debug(s, t, l, ds, dt);

        if (ds >= 0) {
            for (int j = 0; j < LG; ++j) {
                if (ds >> j & 1) {
                    add_edge(up[j][s], i);
                    s = par[j][s];
                }
            }
            s = S[i];
        }

        if (dt >= 0) {
            t = par[0][t];
            for (int j = 0; j < LG; ++j) {
                if (dt >> j & 1) {
                    add_edge(up[j][t], i);
                    t = par[j][t];
                }
            }
            t = T[i];
        }

        if (l != t) {
            add_edge(idt[l], i);
        }
    }

    std::queue<int> que;
    std::vector<int> deg(N + max_node);
    for (int i = 0; i < N + max_node; ++i) {
        for (auto u : bdj[i]) {
            deg[u]++;
        }
    }
    for (int i = 0; i < N + max_node; ++i) {
        if (deg[i] == 0) {
            que.emplace(i);
        }
    }

    while (!que.empty()) {
        auto v = que.front();
        que.pop();
        for (auto u : bdj[v]) {
            if (deg[u]-- == 1) {
                que.emplace(u);
            }
        }
    }

    if (std::accumulate(deg.begin(), deg.end(), 0)) {
        std::cout << "No\n";
    } else {
        std::cout << "Yes\n";
    }
    
    return;
}

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

    int TT = 1; std::cin >> TT;
    for (int i = 1; i <= TT; ++i) {
        solve();
    }

    return 0;
}

• Subtask 1: 5 / 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