oj.uz

Submission #702954

# Submission time Handle Problem Language Result Execution time Memory
702954 2023-02-25T11:23:18 Z piOOE Jail (JOI22_jail) C++17
0 / 100
 1644 ms 1017892 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

class HLD {
public:
    vector<int> par, siz, head, tin, tout, ord, depth;

    int dfs1(int i, vector<vector<int>> &g) {
        for (int &t: g[i]) {
            if (t != par[i]) {
                depth[t] = depth[i] + 1;
                par[t] = i;
                siz[i] += dfs1(t, g);
                if (siz[t] > siz[g[i][0]] || g[i][0] == par[i]) swap(t, g[i][0]);
            }
        }
        return siz[i];
    }

    void dfs2(int i, int &T, const vector<vector<int>> &g) {
        tin[i] = T++;
        for (int t: g[i]) {
            if (t != par[i]) {
                head[t] = (T == tin[i] + 1 ? head[i] : t);
                dfs2(t, T, g);
            }
        }
        tout[i] = T;
    }

    HLD(vector<vector<int>> g, int r = 0)
            : par(g.size(), -1), siz(g.size(), 1), head(g.size(), r), tin(g.size()), ord(g.size()), tout(g.size()),
              depth(g.size()){
        dfs1(r, g);
        int x = 0;
        dfs2(r, x, g);
        for (int i = 0; i < g.size(); ++i) ord[tin[i]] = i;
    }

    vector<pair<int, int>> path(int a, int b) {
        vector<pair<int, int>> res;
        for (;; b = par[head[b]]) {
            if (tin[b] < tin[a]) swap(a, b);
            if (tin[head[b]] <= tin[a]) {
                res.emplace_back(tin[a], tin[b] + 1);
                return res;
            }
            res.emplace_back(tin[head[b]], tin[b] + 1);
        }
    }

    pair<int, int> subtree(int i) {
        return {tin[i], tin[i] + siz[i]};
    }

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

    int lca(int a, int b) {
        for (;; b = par[head[b]]) {
            if (tin[b] < tin[a]) swap(a, b);
            if (tin[head[b]] <= tin[a]) return a;
        }
    }

    bool isp(int a, int b) {
        return tin[a] <= tin[b] && tout[a] >= tout[b];
    }
};

constexpr int N = 1.2e5, D = 256 * 1024;
constexpr int N_ = D + N * 18 * 2 * 2;

vector<int> g[N_];
int top = 0;
int used[N_], in[D], out[D];

int sz = 1;

void init(int n) {
    sz = 1 << __lg(n) + !!(n & (n - 1));

    for (int i = 1; i < sz + n; ++i) {
        in[i] = top++;
        out[i] = top++;
    }
}

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

    HLD tree(adj);

    int m;
    cin >> m;

    top = m;

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

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


    for (int _ = 0; _ < 2; ++_) {
        init(n);

        for (int i = _ ? m - 1 : 0; _ ? i >= 0 : i < m; _ ? --i : ++i) {
            auto [S, T] = prisoner[i];

            for (int x = S + sz; x > 0; x >>= 1) {
                g[in[x]].push_back(i);
                g[in[x]].push_back(top);
                in[x] = top++;
            }

            for (int x = T + sz; x > 0; x >>= 1) {
                g[i].push_back(out[x]);
                g[top].push_back(out[x]);
                out[x] = top++;
            }

            auto path = tree.path(S, T);

            auto dfs = [&](auto dfs, int l, int r, int x, int lx, int rx) {
                if (l >= rx || lx >= r) return;
                if (l <= lx && rx <= r) {
                    g[i].push_back(in[x]);
                    g[out[x]].push_back(i);
                    return;
                }

                int mid = lx + rx >> 1;
                dfs(dfs, l, r, x << 1, lx, mid), dfs(dfs, l, r, x << 1 | 1, mid, rx);
            };

            for (auto [lx, rx] : path) {
                dfs(dfs, lx, rx, 1, 0, sz);
            }
        }
    }

    bool yay = true;

    memset(used, 0, sizeof(used[0]) * top);

    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 < top; ++i) {
        if (!used[i]) {
            dfs(dfs, i);
        }
    }

    for (int i = 0; i < top; ++i) {
        g[i].clear();
    }

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

Compilation message

jail.cpp: In constructor 'HLD::HLD(std::vector<std::vector<int> >, int)':
jail.cpp:8:44: warning: 'HLD::ord' will be initialized after [-Wreorder]
    8 |     vector<int> par, siz, head, tin, tout, ord, depth;
      |                                            ^~~
jail.cpp:8:38: warning:   'std::vector<int> HLD::tout' [-Wreorder]
    8 |     vector<int> par, siz, head, tin, tout, ord, depth;
      |                                      ^~~~
jail.cpp:33:5: warning:   when initialized here [-Wreorder]
   33 |     HLD(vector<vector<int>> g, int r = 0)
      |     ^~~
jail.cpp:39:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for (int i = 0; i < g.size(); ++i) ord[tin[i]] = i;
      |                         ~~^~~~~~~~~~
jail.cpp: In function 'void init(int)':
jail.cpp:84:23: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   84 |     sz = 1 << __lg(n) + !!(n & (n - 1));
      |               ~~~~~~~~^~~~~~~~~~~~~~~~~
jail.cpp: In instantiation of 'solve()::<lambda(auto:23, int, int, int, int, int)> [with auto:23 = solve()::<lambda(auto:23, int, int, int, int, int)>]':
jail.cpp:155:42:   required from here
jail.cpp:150:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  150 |                 int mid = lx + rx >> 1;
      |                           ~~~^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 209464 KB Output is correct
2 Correct 95 ms 209260 KB Output is correct
3 Correct 96 ms 209364 KB Output is correct
4 Correct 113 ms 209416 KB Output is correct
5 Correct 138 ms 209428 KB Output is correct
6 Correct 100 ms 209332 KB Output is correct
7 Correct 97 ms 209464 KB Output is correct
8 Correct 101 ms 209620 KB Output is correct
9 Correct 191 ms 213092 KB Output is correct
10 Correct 148 ms 234824 KB Output is correct
11 Correct 110 ms 209408 KB Output is correct
12 Correct 200 ms 209648 KB Output is correct
13 Correct 808 ms 376856 KB Output is correct
14 Correct 872 ms 382148 KB Output is correct
15 Correct 1466 ms 386328 KB Output is correct
16 Runtime error 1644 ms 1017892 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 209352 KB Output is correct
2 Correct 96 ms 209244 KB Output is correct
3 Correct 96 ms 209340 KB Output is correct
4 Incorrect 98 ms 209360 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 209352 KB Output is correct
2 Correct 96 ms 209244 KB Output is correct
3 Correct 96 ms 209340 KB Output is correct
4 Incorrect 98 ms 209360 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 209352 KB Output is correct
2 Correct 96 ms 209244 KB Output is correct
3 Correct 96 ms 209340 KB Output is correct
4 Incorrect 98 ms 209360 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 209352 KB Output is correct
2 Correct 96 ms 209244 KB Output is correct
3 Correct 96 ms 209340 KB Output is correct
4 Incorrect 98 ms 209360 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 209376 KB Output is correct
2 Correct 101 ms 209360 KB Output is correct
3 Correct 119 ms 209372 KB Output is correct
4 Correct 97 ms 209288 KB Output is correct
5 Correct 114 ms 209324 KB Output is correct
6 Correct 98 ms 209356 KB Output is correct
7 Incorrect 100 ms 209372 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 209464 KB Output is correct
2 Correct 95 ms 209260 KB Output is correct
3 Correct 96 ms 209364 KB Output is correct
4 Correct 113 ms 209416 KB Output is correct
5 Correct 138 ms 209428 KB Output is correct
6 Correct 100 ms 209332 KB Output is correct
7 Correct 97 ms 209464 KB Output is correct
8 Correct 101 ms 209620 KB Output is correct
9 Correct 191 ms 213092 KB Output is correct
10 Correct 148 ms 234824 KB Output is correct
11 Correct 110 ms 209408 KB Output is correct
12 Correct 200 ms 209648 KB Output is correct
13 Correct 808 ms 376856 KB Output is correct
14 Correct 872 ms 382148 KB Output is correct
15 Correct 1466 ms 386328 KB Output is correct
16 Runtime error 1644 ms 1017892 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -