oj.uz

답안 #702956

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
702956 2023-02-25T11:25:00 Z piOOE Jail (JOI22_jail) C++17
0 / 100
 315 ms 274816 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 * 17;

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

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 54312 KB Output is correct
2 Correct 29 ms 54296 KB Output is correct
3 Correct 28 ms 54296 KB Output is correct
4 Correct 48 ms 54448 KB Output is correct
5 Correct 75 ms 54440 KB Output is correct
6 Correct 30 ms 54448 KB Output is correct
7 Correct 30 ms 54484 KB Output is correct
8 Correct 36 ms 54640 KB Output is correct
9 Correct 117 ms 58092 KB Output is correct
10 Correct 81 ms 79892 KB Output is correct
11 Correct 43 ms 54416 KB Output is correct
12 Correct 136 ms 54704 KB Output is correct
13 Runtime error 315 ms 274816 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 54396 KB Output is correct
2 Correct 27 ms 54292 KB Output is correct
3 Correct 31 ms 54356 KB Output is correct
4 Incorrect 32 ms 54396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 54396 KB Output is correct
2 Correct 27 ms 54292 KB Output is correct
3 Correct 31 ms 54356 KB Output is correct
4 Incorrect 32 ms 54396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 54396 KB Output is correct
2 Correct 27 ms 54292 KB Output is correct
3 Correct 31 ms 54356 KB Output is correct
4 Incorrect 32 ms 54396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 54396 KB Output is correct
2 Correct 27 ms 54292 KB Output is correct
3 Correct 31 ms 54356 KB Output is correct
4 Incorrect 32 ms 54396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 54352 KB Output is correct
2 Correct 28 ms 54400 KB Output is correct
3 Correct 28 ms 54336 KB Output is correct
4 Correct 30 ms 54332 KB Output is correct
5 Correct 54 ms 54424 KB Output is correct
6 Correct 33 ms 54356 KB Output is correct
7 Incorrect 28 ms 54356 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 54312 KB Output is correct
2 Correct 29 ms 54296 KB Output is correct
3 Correct 28 ms 54296 KB Output is correct
4 Correct 48 ms 54448 KB Output is correct
5 Correct 75 ms 54440 KB Output is correct
6 Correct 30 ms 54448 KB Output is correct
7 Correct 30 ms 54484 KB Output is correct
8 Correct 36 ms 54640 KB Output is correct
9 Correct 117 ms 58092 KB Output is correct
10 Correct 81 ms 79892 KB Output is correct
11 Correct 43 ms 54416 KB Output is correct
12 Correct 136 ms 54704 KB Output is correct
13 Runtime error 315 ms 274816 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -