제출 #970630

#제출 시각아이디문제언어결과실행 시간메모리
970630BestCrazyNoob늑대인간 (IOI18_werewolf)C++17
100 / 100
589 ms130352 KiB
#include "werewolf.h" #include <vector> #include <utility> #include <array> using namespace std; constexpr int INF = 1e9; constexpr int H = 20; struct DSU { // O(a_inv(m, n)) vector<int> rs; DSU(int n) { rs.resize(n, -1); } int repr(int a) { return rs[a] < 0 ? a : (rs[a] = repr(rs[a])); } bool join(int a, int b) { a = repr(a); b = repr(b); if (a == b) return false; // enforce size(a) > size(b) if (-a < -b) swap(a, b); rs[a] += rs[b]; rs[b] = a; return true; } }; struct DSU2 { // O(log(n)) vector<int> rs; DSU2(int n) { rs.resize(n, -1); } int repr(int a) { return rs[a] < 0 ? a : (rs[a] = repr(rs[a])); } // a will become the repr int join(int a, int b) { a = repr(a); b = repr(b); // use given order rs[a] += rs[b]; rs[b] = a; return b; // after call to repr() } }; struct SegTree { vector<int> tree; int sz; int ql, qr; SegTree() {} SegTree(int n) { sz = 1; while (sz < n) sz *= 2; tree.resize(2*sz, -1); } int __query(int ni, int nl, int nr) { if (qr <= nl || nr <= ql) return -1; if (ql <= nl && nr <= qr) return tree[ni]; int nm = (nl+nr)/2; return max(__query(2*ni, nl, nm), __query(2*ni+1, nm, nr)); } int query(int l, int r) { ql = l; qr = r; return __query(1, 0, sz); } void set(int i, int x) { i += sz; tree[i] = x; while (i > 1) { i /= 2; tree[i] = max(tree[2*i], tree[2*i+1]); } } }; vector<vector<int>> graph, adj0, adj1; vector<int> tin0, tin1, tout0, tout1, ans; int N, M, curr_eul; SegTree seg; vector<array<int, H>> anc0, anc1; // other, q_index vector<vector<pair<int, int>>> queries; void setup0() { DSU dsu(N); DSU2 maxel(N); adj0.resize(N); for (int i = 0; i < N; ++i) { for (int x: graph[i]) { if (x > i || !dsu.join(i, x)) continue; const int other = maxel.join(i, x); adj0[i].push_back(other); adj0[other].push_back(i); } } } void setup1() { DSU dsu(N); DSU2 maxel(N); adj1.resize(N); for (int i = N-1; i >= 0; --i) { for (int x: graph[i]) { if (x < i || !dsu.join(i, x)) continue; const int other = maxel.join(i, x); adj1[i].push_back(other); adj1[other].push_back(i); } } } void euler(int curr, int prev, vector<vector<int>> &adj, vector<int> &tin, vector<int> &tout, vector<array<int, H>> &anc) { tin[curr] = curr_eul++; for (int x: adj[curr]) { if (x == prev) continue; anc[x][0] = curr; euler(x, curr, adj, tin, tout, anc); } tout[curr] = curr_eul; } void calc_anc(vector<array<int, H>> &anc) { for (int h = 0; h < H-1; ++h) { for (auto &arr: anc) { arr[h+1] = arr[h] == -1 ? -1 : anc[arr[h]][h]; } } } int get_anc0(int x, int d) { for (int h = H-1; h >= 0; --h) { if (anc0[x][h] != -1 && anc0[x][h] <= d) x = anc0[x][h]; } return x; } int get_anc1(int x, int d) { for (int h = H-1; h >= 0; --h) { if (anc1[x][h] != -1 && anc1[x][h] >= d) x = anc1[x][h]; } return x; } void answer(int curr, int prev) { for (int x: adj0[curr]) { if (x == prev) continue; answer(x, curr); } // mark the current node visited and say when it was visited seg.set(tin1[curr], tin0[curr]); for (auto [other, q_index]: queries[curr]) { ans[q_index] = seg.query(tin1[other], tout1[other]) >= tin0[curr]; } } vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) { const int Q = S.size(); M = X.size(); ::N = N; graph.resize(N); for (int m = 0; m < M; ++m) { graph[X[m]].push_back(Y[m]); graph[Y[m]].push_back(X[m]); } // trasform into tree setup0(); setup1(); anc0.resize(N); tin0.resize(N); tout0.resize(N); anc0[N-1][0] = -1; curr_eul = 0; euler(N-1, -1, adj0, tin0, tout0, anc0); calc_anc(anc0); anc1.resize(N); tin1.resize(N); tout1.resize(N); anc1[0][0] = -1; curr_eul = 0; euler(0, -1, adj1, tin1, tout1, anc1); calc_anc(anc1); ans.resize(Q); queries.resize(N); for (int q = 0; q < Q; ++q) { queries[get_anc0(E[q], R[q])].push_back({get_anc1(S[q], L[q]), q}); } seg = SegTree(N); answer(N-1, -1); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...