oj.uz

Submission #936132

# Submission time Handle Problem Language Result Execution time Memory
936132 2024-03-01T08:09:16 Z Pannda Jail (JOI22_jail) C++17
0 / 100
 16 ms 856 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 16 ms 856 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 2 ms 464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 2 ms 464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 2 ms 464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 2 ms 464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 7 ms 604 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 16 ms 856 KB Output isn't correct
5 Halted 0 ms 0 KB -