Submission #702937

#	Time	Username	Problem	Language	Result	Execution time	Memory
702937		piOOE	Jail (JOI22_jail)	C++17	61 / 100	5079 ms	33552 KiB

jail

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct staticLCA {
    vector<int> depth, ord, tin;
    vector<vector<int>> st;
    int n{}, root = 0;

    void dfs(int v, int p, vector<vector<int>> &g) {
        if (v != root) {
            depth[v] = depth[p] + 1;
        }

        tin[v] = ord.size();
        ord.push_back(v);
        for (int to: g[v]) {
            if (to != p) {
                dfs(to, v, g);
                ord.push_back(v);
            }
        }
    }

    int func(int a, int b) {
        return depth[a] < depth[b] ? a : b;
    }

    staticLCA(vector<vector<int>> &g, int _root = 0) {
        init(g, _root);
    }

    staticLCA() = default;

    void init(vector<vector<int>> &g, int _root = 0) {
        n = g.size();
        root = _root;
        depth.assign(n, 0);
        tin.resize(n);

        dfs(root, -1, g);

        int m = ord.size();
        int logn = __lg(m) + 1;

        st.resize(logn);
        st[0] = ord;

        for (int j = 1; j < logn; ++j) {
            st[j].resize(m - (1 << j) + 1);
            for (int i = 0; i <= m - (1 << j); ++i) {
                st[j][i] = func(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    int lca(int a, int b) {
        int L = min(tin[a], tin[b]), R = max(tin[a], tin[b]) + 1;
        int lg = __lg(R - L);
        return func(st[lg][L], st[lg][R - (1 << lg)]);
    }

    int lca(int a, int b, int c) {
        return lca(a, b) ^ lca(a, c) ^ lca(b, c);
    }

    int dist(int a, int b) {
        return depth[a] + depth[b] - depth[lca(a, b)] * 2;
    }
};

void solve() {
    int n;
    cin >> n;

    vector<vector<int>> adj(n);

    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        a -= 1, b -= 1;

        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    staticLCA tree(adj);

    int m;
    cin >> m;

    vector<array<int, 2>> prisoner(m);

    for (auto &[s, t] : prisoner) {
        cin >> s >> t;
        s -= 1, t -= 1;
    }

    vector<vector<int>> g(m);

    for (int i = 0; i < m; ++i) {
        auto [s, t] = prisoner[i];

        for (int j = 0; j < m; ++j) {
            if (j != i) {
                auto [x, y] = prisoner[j];

                if (tree.lca(s, t, x) == x) {
                    g[i].push_back(j);
                }

                if (tree.lca(s, t, y) == y) {
                    g[j].push_back(i);
                }
            }
        }
    }

    bool yay = true;

    vector<int> used(m);

    auto dfs = [&](auto self, int v) -> void {
        used[v] = 1;

        for (int to : g[v]) {
            if (!used[to]) {
                self(self, to);
            } else if (used[to] == 1) {
                yay = false;
            }
        }

        used[v] = 2;
    };

    for (int i = 0; i < m; ++i) {
        if (!used[i]) {
            dfs(dfs, i);
        }
    }

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

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

    int test = 1;
    cin >> test;

    while (test--) {
        solve();
    }

    return 0;
}

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