Submission #937058

#	Time	Username	Problem	Language	Result	Execution time	Memory
937058		Pannda	Jail (JOI22_jail)	C++17	100 / 100	1589 ms	341212 KiB

jail

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

struct Tree {
    int log, idx;
    vector<int> depth;
    vector<vector<int>> lift;
    vector<vector<int>> f;
    vector<array<int, 2>> edges;

    Tree(int n, vector<vector<int>> &adj, int root = 0) : log(32 - __builtin_clz(n)), idx(0), depth(n), lift(n, vector<int>(log, -1)), f(n, vector<int>(log, -1)) {
        auto dfs = [&](auto self, int u, int p) -> void {
            for (int v : adj[u]) {
                if (v == p) continue;
                depth[v] = depth[u] + 1;
                lift[v][0] = u;
                f[v][0] = idx++;
                for (int i = 1; i < log; i++) {
                    int w = lift[v][i - 1];
                    if (w != -1) {
                        lift[v][i] = lift[w][i - 1];
                        if (f[w][i - 1] != -1) f[v][i] = idx++;
                        if (f[w][i - 1] != -1) edges.push_back({f[v][i], f[v][i - 1]});
                        if (f[w][i - 1] != -1) edges.push_back({f[v][i], f[w][i - 1]});
                    }
                }
                self(self, v, u);
            }
        };
        depth[root] = 0;
        f[root][0] = idx++;
        dfs(dfs, root, -1);
    }

    int count() {
        return idx;
    }

    vector<array<int, 2>> getEdges() {
        return edges;
    }

    int lca(int u, int v) {
        if (depth[u] > depth[v]) swap(u, v);
        for (int i = log - 1; i >= 0; i--) {
            int w = lift[v][i];
            if (w != -1 && depth[w] >= depth[u]) v = w;
        }
        if (u == v) return u;
        for (int i = log - 1; i >= 0; i--) {
            if (lift[u][i] != lift[v][i]) {
                u = lift[u][i];
                v = lift[v][i];
            }
        }
        return lift[u][0];
    }

    int getIntermediate(int s, int t) { // not to take s == t
        int m = lca(s, t);
        if (s != m) return lift[s][0];
        for (int i = log - 1; i >= 0; i--) {
            int w = lift[t][i];
            if (w != -1 && depth[w] > depth[s]) t = w;
        }
        return t;
    }

    int getNode(int u) {
        return f[u][0];
    }

    vector<int> getPath(int u, int v) {
        vector<int> res;
        if (depth[u] > depth[v]) swap(u, v);
        for (int i = log - 1; i >= 0; i--) {
            int w = lift[v][i];
            if (w != -1 && depth[w] >= depth[u]) {
                res.push_back(f[v][i]);
                v = w;
            }
        }
        if (u == v) {
            res.push_back(f[u][0]);
            return res;
        }
        for (int i = log - 1; i >= 0; i--) {
            if (lift[u][i] != lift[v][i]) {
                res.push_back(f[u][i]);
                res.push_back(f[v][i]);
                u = lift[u][i];
                v = lift[v][i];
            }
        }
        res.push_back(f[u][1]);
        res.push_back(f[v][0]);
        return res;
    }
};

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);
        }

        int m;
        cin >> m;

        Tree tree(n, adj);
        vector<vector<int>> dag(2 * tree.count() + m);
        for (auto [u, v] : tree.getEdges()) {
            dag[v].push_back(u);
            dag[tree.count() + u].push_back(tree.count() + v);
        }

        for (int i = 0; i < m; i++) {
            int s, t;
            cin >> s >> t;
            s--;
            t--;
            int u = 2 * tree.count() + i;
            dag[u].push_back(tree.getNode(s));
            dag[u].push_back(tree.count() + tree.getNode(s));
            dag[tree.getNode(t)].push_back(u);
            dag[tree.count() + tree.getNode(t)].push_back(u);
            s = tree.getIntermediate(s, t);
            if (s == t) continue;
            t = tree.getIntermediate(t, s);
            vector<int> path = tree.getPath(s, t);
            for (int v : path) {
                dag[v].push_back(u);
                dag[u].push_back(tree.count() + v);
            }
        }

        vector<int> deg(2 * tree.count() + m, 0);
        for (int u = 0; u < 2 * tree.count() + m; u++) {
            for (int v : dag[u]) {
                deg[v]++;
            }
        }

        vector<int> que;
        for (int u = 0; u < 2 * tree.count() + m; u++) {
            if (!deg[u]) {
                que.push_back(u);
            }
        }

        for (int i = 0; i < que.size(); i++) {
            int u = que[i];
            for (int v : dag[u]) {
                if (!--deg[v]) {
                    que.push_back(v);
                }
            }
        }

        que.size() == 2 * tree.count() + m ? cout << "Yes\n" : cout << "No\n";

    }
}

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:165:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |         for (int i = 0; i < que.size(); i++) {
      |                         ~~^~~~~~~~~~~~
jail.cpp:174:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  174 |         que.size() == 2 * tree.count() + m ? cout << "Yes\n" : cout << "No\n";
      |         ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• 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