oj.uz

Submission #702953

# Submission time Handle Problem Language Result Execution time Memory
702953 2023-02-25T11:22:52 Z piOOE Jail (JOI22_jail) C++17
0 / 100
 567 ms 517844 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;

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 62 ms 107820 KB Output is correct
2 Correct 54 ms 107844 KB Output is correct
3 Correct 52 ms 107892 KB Output is correct
4 Correct 73 ms 108212 KB Output is correct
5 Correct 95 ms 108636 KB Output is correct
6 Correct 56 ms 107952 KB Output is correct
7 Correct 70 ms 107980 KB Output is correct
8 Correct 63 ms 108256 KB Output is correct
9 Correct 215 ms 112928 KB Output is correct
10 Correct 107 ms 134896 KB Output is correct
11 Correct 72 ms 108084 KB Output is correct
12 Correct 169 ms 109176 KB Output is correct
13 Runtime error 567 ms 517844 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 107920 KB Output is correct
2 Correct 53 ms 107916 KB Output is correct
3 Correct 60 ms 108004 KB Output is correct
4 Incorrect 56 ms 108008 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 107920 KB Output is correct
2 Correct 53 ms 107916 KB Output is correct
3 Correct 60 ms 108004 KB Output is correct
4 Incorrect 56 ms 108008 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 107920 KB Output is correct
2 Correct 53 ms 107916 KB Output is correct
3 Correct 60 ms 108004 KB Output is correct
4 Incorrect 56 ms 108008 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 107920 KB Output is correct
2 Correct 53 ms 107916 KB Output is correct
3 Correct 60 ms 108004 KB Output is correct
4 Incorrect 56 ms 108008 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 107900 KB Output is correct
2 Correct 53 ms 107924 KB Output is correct
3 Correct 54 ms 107988 KB Output is correct
4 Correct 52 ms 107832 KB Output is correct
5 Correct 79 ms 108104 KB Output is correct
6 Correct 60 ms 107980 KB Output is correct
7 Incorrect 57 ms 107948 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 107820 KB Output is correct
2 Correct 54 ms 107844 KB Output is correct
3 Correct 52 ms 107892 KB Output is correct
4 Correct 73 ms 108212 KB Output is correct
5 Correct 95 ms 108636 KB Output is correct
6 Correct 56 ms 107952 KB Output is correct
7 Correct 70 ms 107980 KB Output is correct
8 Correct 63 ms 108256 KB Output is correct
9 Correct 215 ms 112928 KB Output is correct
10 Correct 107 ms 134896 KB Output is correct
11 Correct 72 ms 108084 KB Output is correct
12 Correct 169 ms 109176 KB Output is correct
13 Runtime error 567 ms 517844 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -