Submission #702978

#	Time	Username	Problem	Language	Result	Execution time	Memory
702978		piOOE	Jail (JOI22_jail)	C++17	100 / 100	1122 ms	145164 KiB

jail

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


    init(n);

    vector<vector<pair<int, int>>> same(n);

    for (int i = 0; i < m; ++i) {
        auto [S, T] = prisoner[i];

        if (S != T) {
            same[S].push_back({i, 0});
            same[T].push_back({i, 1});
        }

        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) {
            if (lx == tree.tin[S]) lx++;
            if (rx == tree.tin[S] + 1) --rx;
            if (lx == tree.tin[T]) lx++;
            if (rx == tree.tin[T] + 1) --rx;

            assert(!(lx <= tree.tin[S] && tree.tin[S] < rx));
            assert(!(lx <= tree.tin[T] && tree.tin[T] < rx));

            if (lx < rx) {
                dfs(dfs, lx, rx, 1, 0, sz);
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        if (same[i].size() == 2) {
            if (same[i][0].second == 0) {
                swap(same[i][0], same[i][1]);
            }

            g[same[i][0].first].push_back(same[i][1].first);
        }
    }

    for (int i = 0; i < m; ++i) {
        auto [S, T] = prisoner[i];

        S = tree.tin[S];
        T = tree.tin[T];

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

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

    bool yay = true;

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

    vector<int> stk;

    auto dfs = [&](auto self, int v) -> void {
        used[v] = 1;
        if (v < m) stk.push_back(v);

        for (int to: g[v]) {
            if (!used[to]) {
                self(self, to);
            } else if (used[to] == 1 && stk.back() != to) {
                yay = false;
            }
        }

        used[v] = 2;
        if (v < m) stk.pop_back();
    };

    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 (stderr)

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:158:42:   required from here
jail.cpp:144:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  144 |             int mid = lx + rx >> 1;
      |                       ~~~^~~~

• 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