제출 #600745

#제출 시각아이디문제언어결과실행 시간메모리
600745piOOE늑대인간 (IOI18_werewolf)C++17
100 / 100
1666 ms233424 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; const int inf = 1e9 + 7; struct dsu { vector<int> p; dsu() = default; dsu(int n) { p.resize(n); iota(p.begin(), p.end(), 0); } int get(int a) { return a == p[a] ? a : p[a] = get(p[a]); } bool mrg(int a, int b) { a = get(a); b = get(b); if (a == b) { return false; } p[b] = a; return true; } bool same(int a, int b) { return get(a) == get(b); } }; struct SegTree { int sz = 1; vector<vector<int>> t; SegTree() = default; SegTree(const vector<int> &a) { int n = (int) a.size(); sz = 1; while (sz < n) sz <<= 1; t.assign(sz << 1, {}); for (int i = 0; i < n; ++i) { t[i + sz] = {a[i]}; } for (int i = sz - 1; i > 0; --i) { t[i].resize(t[i << 1].size() + t[i << 1 | 1].size()); merge(t[i << 1].begin(), t[i << 1].end(), t[i << 1 | 1].begin(), t[i << 1 | 1].end(), t[i].begin()); } } int get(int l, int r, int val, int x, int lx, int rx) { if (l >= rx || lx >= r) return inf; if (l <= lx && rx <= r) { auto it = lower_bound(t[x].begin(), t[x].end(), val); if (it == t[x].end()) { return inf; } else { return *it; } } int m = (lx + rx) >> 1; return min(get(l, r, val, x << 1, lx, m), get(l, r, val, x << 1 | 1, m, rx)); } }; namespace Werewolf { const int N = 600000, logn = 20; int jump[logn][N], weight[N], tin[N], tout[N], T = 0; vector<int> g[N], ord; int n, m; void init(vector<array<int, 3>> e, int _n) { n = _n; m = (int)e.size(); dsu d(n + m); int last = n; assert(*max_element(tin, tin + N) == 0); for (auto [w, a, b] : e) { if (d.same(a, b)) { g[last].push_back(d.get(a)); d.mrg(last, a); } else { g[last].push_back(d.get(a)); g[last].push_back(d.get(b)); d.mrg(last, a); d.mrg(last, b); } weight[last - n] = w; last += 1; } function<void(int)> dfs = [&](int v) { tin[v] = T; if (v < n) { ord.push_back(v); T++; } for (int to : g[v]) { jump[0][to] = v; dfs(to); } tout[v] = T; }; memset(tin, -1, sizeof(tin)); for (int i = last - 1; i > -1; --i) { if (tin[i] == -1) { jump[0][i] = i; dfs(i); } } for (int j = 1; j < logn; ++j) { for (int i = 0; i < n + m; ++i) { jump[j][i] = jump[j - 1][jump[j - 1][i]]; } } } pair<int, int> get(int v, int w) { for (int j = logn - 1; j > -1; --j) { if (weight[jump[j][v] - n] <= w) { v = jump[j][v]; } } return {tin[v], tout[v]}; } }; namespace Human { const int N = 600000, logn = 20; int jump[logn][N], weight[N], tin[N], tout[N], T = 0; vector<int> g[N], ord; int n, m; void init(vector<array<int, 3>> e, int _n) { n = _n; m = (int)e.size(); dsu d(n + m); int last = n; assert(*max_element(tin, tin + N) == 0); for (auto [w, a, b] : e) { if (d.same(a, b)) { g[last].push_back(d.get(a)); d.mrg(last, a); } else { g[last].push_back(d.get(a)); g[last].push_back(d.get(b)); d.mrg(last, a); d.mrg(last, b); } weight[last - n] = w; last += 1; } function<void(int)> dfs = [&](int v) { tin[v] = T; if (v < n) { ord.push_back(v); T++; } for (int to : g[v]) { jump[0][to] = v; dfs(to); } tout[v] = T; }; memset(tin, -1, sizeof(tin)); for (int i = last - 1; i > -1; --i) { if (tin[i] == -1) { jump[0][i] = i; dfs(i); } } for (int j = 1; j < logn; ++j) { for (int i = 0; i < n + m; ++i) { jump[j][i] = jump[j - 1][jump[j - 1][i]]; } } } pair<int, int> get(int v, int w) { for (int j = logn - 1; j > -1; --j) { if (weight[jump[j][v] - n] >= w) { v = jump[j][v]; } } return {tin[v], tout[v]}; } } //human vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> s, vector<int> e, vector<int> L, vector<int> R) { int m = (int)X.size(), q = (int)e.size(); vector<array<int, 3>> eWerewolf(m), eHuman(m); for (int i = 0; i < m; ++i) { if (X[i] > Y[i]) { swap(X[i], Y[i]); } eWerewolf[i] = {Y[i], X[i], Y[i]}; eHuman[i] = {X[i], X[i], Y[i]}; } sort(eHuman.begin(), eHuman.end(), greater()); sort(eWerewolf.begin(), eWerewolf.end()); Werewolf::init(eWerewolf, n); Human::init(eHuman, n); vector<int> a(n); for (int i = 0; i < n; ++i) { a[i] = Human::tin[Werewolf::ord[i]]; } SegTree st(a); vector<int> ans(q); for (int i = 0; i < q; ++i) { auto [hL, hR] = Human::get(s[i], L[i]); auto [wL, wR] = Werewolf::get(e[i], R[i]); int x = st.get(wL, wR, hL, 1, 0, st.sz); ans[i] = (x < hR); } 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...