제출 #815427

#제출 시각아이디문제언어결과실행 시간메모리
815427erray늑대인간 (IOI18_werewolf)C++17
100 / 100
448 ms79488 KiB
#include "werewolf.h" //author: erray #include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "/home/ioi/codes/debug.h" #else #define debug(...) (void) 37 #endif struct DSU { vector<int> link; DSU(int n) { link.resize(n); iota(link.begin(), link.end(), 0); } int get(int v) { return link[v] = (v == link[v] ? v : get(link[v])); } bool unite(int x, int y) { x = get(x), y = get(y); if (x == y) { return false; } link[y] = x; return true; } }; struct SegTree { vector<int> mx; int n; SegTree(int _n) : n(_n) { mx.resize(2 * n + 1, -1); } int get(int l, int r) { int res = -1; for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) { debug(l, r, mx[l], mx[r - 1]); if (l & 1) { res = max(res, mx[l++]); } if (r & 1) { res = max(res, mx[--r]); } } return res; } void modify(int x, int v) { for (mx[x += n] = v; x > 1; x >>= 1) { mx[x >> 1] = max(mx[x], mx[x ^ 1]); } } }; std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) { int M = int(X.size()); int Q = int(S.size()); vector<vector<int>> g(N); for (int i = 0; i < M; ++i) { g[X[i]].push_back(Y[i]); g[Y[i]].push_back(X[i]); } debug(N, g); auto Convert_to_array = [&](bool rev, vector<int> end, vector<int> ver) { vector<int> ord(N); iota(ord.begin(), ord.end(), 0); if (rev) { reverse(ord.begin(), ord.end()); } debug(ord); DSU d(N); const int LG = __lg(N) + 1; vector<vector<int>> lift(LG, vector<int>(N, -1)); vector<vector<int>> ch(N); for (auto v : ord) { for (auto u : g[v]) { if ((u < v) ^ rev && d.get(v) != d.get(u)) { ch[v].push_back(d.get(u)); lift[0][d.get(u)] = v; d.unite(v, u); } } } debug(ch, lift); for (int l = 1; l < LG; ++l) { for (int i = 0; i < N; ++i) { int go = lift[l - 1][i]; lift[l][i] = (go == -1 ? -1 : lift[l - 1][go]); } } vector<int> tin(N), tout(N), tour; function<void(int)> Dfs = [&](int v) { tin[v] = int(tour.size()); tour.push_back(v); for (auto u : ch[v]) { Dfs(u); } tout[v] = int(tour.size()) - 1; }; Dfs(ord.back()); debug(tin, tout, lift); vector<int> tour_l(Q), tour_r(Q); for (int i = 0; i < Q; ++i) { int v = ver[i]; for (int l = LG - 1; l >= 0; --l) { if (lift[l][v] != -1 && (!rev? lift[l][v] <= end[i] : lift[l][v] >= end[i])) { v = lift[l][v]; } } tour_l[i] = tin[v]; tour_r[i] = tout[v]; } return make_tuple(tour, tour_l, tour_r); }; auto[end_tour, end_l, end_r] = Convert_to_array(false, R, E); auto[start_tour, start_l, start_r] = Convert_to_array(true, L, S); debug(end_tour, end_l, end_r); debug(start_tour, start_l, start_r); vector<vector<int>> qs(N); for (int i = 0; i < Q; ++i) { qs[end_r[i]].push_back(i); } vector<int> ind(N); for (int i = 0; i < N; ++i) { ind[start_tour[i]] = i; } debug(qs, ind); SegTree st(N); vector<int> ans(Q); for (int i = 0; i < N; ++i) { st.modify(ind[end_tour[i]], i); debug(ind[end_tour[i]], i); for (auto q : qs[i]) { int mx = st.get(start_l[q], start_r[q]); debug(mx, start_l[q], start_r[q]); ans[q] = (mx >= end_l[q]); } } 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...