Submission #936132

#	Time	Username	Problem	Language	Result	Execution time	Memory
936132		Pannda	Jail (JOI22_jail)	C++17	0 / 100	16 ms	856 KiB

jail

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

struct Tree {
    vector<int> siz, parent, depth, head, begin, end;

    Tree(int n, vector<vector<int>> &adj) : siz(n), parent(n), depth(n), head(n), begin(n), end(n) {
        auto dfs = [&](auto self, int u, int p) -> void {
            siz[u] = 1;
            parent[u] = p;
            depth[u] = p == -1 ? 0 : depth[p] + 1;
            for (int v : adj[u]) {
                if (v == p) continue;
                self(self, v, u);
                siz[u] += siz[v];
            }
        };
        dfs(dfs, 0, -1);
        int tim = 0;
        auto decompose = [&](auto self, int u, int h) -> void {
            head[u] = h;
            begin[u] = tim++;
            int heavy = -1;
            for (int v : adj[u]) {
                if (v == parent[u]) continue;
                if (heavy == -1 || siz[v] > siz[heavy]) heavy = v;
            }
            if (heavy != -1) self(self, heavy, h);
            for (int v : adj[u]) {
                if (v == parent[u] || v == heavy) continue;
                self(self, v, v);
            }
            end[u] = tim;
        };
        decompose(decompose, 0, 0);
    }

    int getNode(int u) {
        return begin[u];
    }

    vector<array<int, 2>> getPath(int u, int v) {
        vector<array<int, 2>> res;
        for (; head[u] != head[v]; v = parent[head[v]]) {
            if (depth[head[u]] > depth[head[v]]) swap(u, v);
            res.push_back({begin[head[v]], begin[v] + 1});
        }
        if (depth[u] > depth[v]) swap(u, v);
        res.push_back({begin[u], begin[v] + 1});
        return res;
    }
};

template <class T>
struct SegmentTree {
    int n;
    vector<pair<T, int>> mn;
    vector<T> lazy;

    SegmentTree(int n) : n(n), mn(4 * n), lazy(4 * n, 0) {
        auto build = [&](auto self, int idx, int l, int r) -> void {
            if (l + 1 == r) {
                mn[idx] = {0, l};
            } else {
                int m = (l + r) >> 1;
                self(self, 2 * idx + 1, l, m);
                self(self, 2 * idx + 2, m, r);
                mn[idx] = min(mn[2 * idx + 1], mn[2 * idx + 2]);
            }
        };
        build(build, 0, 0, n);
    }

    void apply(int idx, T delta) {
        mn[idx].first += delta;
        lazy[idx] += delta;
    }

    void add(int ql, int qr, T delta) {
        auto dfs = [&](auto self, int idx, int l, int r) -> void {
            if (r <= ql || qr <= l) return;
            if (ql <= l && r <= qr) return apply(idx, delta);
            apply(2 * idx + 1, lazy[idx]);
            apply(2 * idx + 2, lazy[idx]);
            lazy[idx] = 0;
            int m = (l + r) >> 1;
            self(self, 2 * idx + 1, l, m);
            self(self, 2 * idx + 2, m, r);
            mn[idx] = min(mn[2 * idx + 1], mn[2 * idx + 2]);
        };
        dfs(dfs, 0, 0, n);
    }

    pair<T, int> getMin() {
        return mn[0];
    }
};

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

    int t;
    cin >> t;
    while (t--) {

        int n;
        cin >> n;
        vector<vector<int>> adj(n);
        for (int i = 0; i < n - 1; i++) {
            int u, v;
            cin >> u >> v;
            u--;
            v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        Tree tree(n, adj);
        SegmentTree<int> seg(n);
        vector<int> inv(n);
        for (int u = 0; u < n; u++) inv[tree.getNode(u)] = u;

        int m;
        cin >> m;
        vector<int> f(n, -1);
        for (int i = 0; i < m; i++) {
            int s, t;
            cin >> s >> t;
            s--;
            t--;
            f[t] = s;
            vector<array<int, 2>> path = tree.getPath(s, t);
            for (auto [l, r] : path) seg.add(l, r, +1);
        }

        vector<bool> good(n, false);
        while (true) {
            auto [mn, pos] = seg.getMin();
            if (mn > 1) break;
            seg.add(pos, pos + 1, +1e9);
            int t = inv[pos];
            int s = f[t];
            if (s == -1) continue;
            good[t] = true;
            vector<array<int, 2>> path = tree.getPath(s, t);
            for (auto [l, r] : path) seg.add(l, r, -1);
        }

        count(good.begin(), good.end(), true) == m ? cout << "Yes\n" : cout << "No\n";

    }
}

• 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