Submission #1176088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176088		MisterReaper	Jail (JOI22_jail)	C++20	100 / 100	808 ms	296356 KiB

jail

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG
    #include "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<std::array<int, 2>> X(M);
    for (int i = 0; i < M; ++i) {
        std::cin >> X[i][0] >> X[i][1];
        --X[i][0], --X[i][1];
    }

    std::vector<int> invA(N, -1), invB(N, -1);
    for (int i = 0; i < M; ++i) {
        invA[X[i][0]] = i;
        invB[X[i][1]] = i;
    }

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

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

    for (int l = 0; l < LG - 1; ++l) {
        for (int i = 0; i < N; ++i) {
            if (par[l][i] != -1){ 
                par[l + 1][i] = par[l][par[l][i]];
            }
        }
    }

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

    int node_alloc = M;
    std::vector<std::vector<int>> tableup(LG, std::vector<int>(N));
    std::vector<std::vector<int>> tabledw(LG, std::vector<int>(N));
    for (int i = 0; i < LG; ++i) {
        for (int j = 0; j < N; ++j) {
            tableup[i][j] = node_alloc++;
            tabledw[i][j] = node_alloc++;
        }
    }
    
    debug("wtf", __LINE__);

    std::vector<int> deg(node_alloc);
    std::vector<std::vector<int>> bdj(node_alloc);
    auto add_restriction = [&](int a, int b) -> void {
        deg[b]++;
        bdj[a].emplace_back(b);
    };

    for (int i = 0; i < N; ++i) {
        if (invB[i] != -1) {
            add_restriction(tabledw[0][i], invB[i]);
        }
        if (invA[i] != -1) {
            add_restriction(invA[i], tableup[0][i]);
        }
    }

    debug("wtf", __LINE__);

    for (int i = 0; i < LG - 1; ++i) {
        for (int j = 0; j < N; ++j) {
            int k = par[i][j];
            add_restriction(tabledw[i + 1][j], tabledw[i][j]);
            if (k != -1) {
                add_restriction(tabledw[i + 1][j], tabledw[i][k]);
            }
            add_restriction(tableup[i][j], tableup[i + 1][j]);
            if (k != -1) {
                add_restriction(tableup[i][k], tableup[i + 1][j]);
            }
        }
    }

    debug("wtf", __LINE__);

    auto add_interval = [&](int v, int x, int ori) -> void {
        debug(v, x);
        for (int i = 0; i < LG; ++i) {
            if (x >> i & 1) {
                add_restriction(tableup[i][v], ori);
                add_restriction(ori, tabledw[i][v]);
                v = par[i][v];
            }
        }
    };

    for (int i = 0; i < M; ++i) {
        int u = X[i][0], v = X[i][1];
        int l = lca(u, v);
        debug(u, v, l);
        if (dep[u] - dep[l] - (l == v) >= 0) {
            add_interval(par[0][u], dep[u] - dep[l] - (l == v), i);
        }
        if (dep[v] - dep[l] - (l == u) >= 0) {
            add_interval(par[0][v], dep[v] - dep[l] - (l == u), i);
        }
        if (invA[v] != -1) {
            add_restriction(invA[v], i);
        }
        if (invB[u] != -1) {
            add_restriction(i, invB[u]);
        }
    }

    debug("wtf", __LINE__);

    std::queue<int> que;
    for (int i = 0; i < node_alloc; ++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] == 0) {
                que.emplace(u);
            }
        }
    }

    if (std::count(deg.begin(), deg.end(), 0) != node_alloc) {
        std::cout << "No\n";
    } else {
        std::cout << "Yes\n";
    }
}

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

    int TT;
    std::cin >> TT;
    while (TT--) {
        solve();
    }

    return 0;
}

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