Submission #688596

#TimeUsernameProblemLanguageResultExecution timeMemory
688596bebraWerewolf (IOI18_werewolf)C++17
100 / 100
2217 ms97796 KiB
#include <bits/stdc++.h> #include "werewolf.h" using namespace std; #define dbg(x) cerr << #x << ": " << x << endl; struct DSU { vector<int> parent; vector<vector<int>> tree; vector<vector<int>> binup; vector<int> tin; vector<int> tout; vector<int> vertices; int n; int max_k; int timer; DSU(int _n) : n(_n) { parent.resize(n); iota(parent.begin(), parent.end(), 0); tree.resize(n); tin.resize(n); tout.resize(n); vertices.resize(n); timer = 0; max_k = __lg(n) + 2; binup.assign(max_k, vector<int>(n)); } int find(int v) { if (parent[v] == v) { return v; } else { return parent[v] = find(parent[v]); } } void unite(int u, int v) { u = find(u); assert(parent[v] == v); if (u == v) return; tree[v].push_back(u); parent[u] = v; } void dfs(int v) { vertices[timer] = v; tin[v] = timer++; for (auto u : tree[v]) { binup[0][u] = v; for (int k = 1; k < max_k; ++k) { binup[k][u] = binup[k - 1][binup[k - 1][u]]; } dfs(u); } tout[v] = timer - 1; } void traverse() { for (int v = 0; v < n; ++v) { if (parent[v] == v) { for (int k = 0; k < max_k; ++k) { binup[k][v] = v; } dfs(v); } } } }; struct Query { static const int BLOCK_SIZE = 450; int l; int r; int idx; int block; Query(int _l = 0, int _r = 0, int _idx = 0) : l(_l), r(_r), idx(_idx) { block = l / BLOCK_SIZE; } bool operator<(const Query& other) const { return tie(block, r) < tie(other.block, other.r); } }; struct FenwickTree { vector<int> tree; int n; FenwickTree(int _n) : n(_n) { tree.resize(n); } void update(int pos, int value) { for (int i = pos; i < n; i |= i + 1) { tree[i] += value; } } int query(int l, int r) { int res = 0; for (int i = r; i >= 0; i = (i & (i + 1)) - 1) { res += tree[i]; } for (int i = l - 1; i >= 0; i = (i & (i + 1)) - 1) { res -= tree[i]; } return res; } }; vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> f, vector<int> ls, vector<int> rs) { vector<vector<int>> g(n); int m = x.size(); for (int i = 0; i < m; ++i) { int u = x[i]; int v = y[i]; g[u].push_back(v); g[v].push_back(u); } DSU dsu_right(n); for (int v = 0; v < n; ++v) { for (auto u : g[v]) { if (u > v) continue; dsu_right.unite(u, v); } } DSU dsu_left(n); for (int v = n - 1; v >= 0; --v) { for (auto u : g[v]) { if (u < v) continue; dsu_left.unite(u, v); } } dsu_right.traverse(); dsu_left.traverse(); int q = s.size(); vector<int> ans(q); vector<Query> queries(q); for (int i = 0; i < q; ++i) { int v = f[i]; for (int k = dsu_right.max_k - 1; k >= 0; --k) { if (dsu_right.binup[k][v] < rs[i]) { v = dsu_right.binup[k][v]; } } if (dsu_right.binup[0][v] <= rs[i]) v = dsu_right.binup[0][v]; queries[i] = Query(dsu_right.tin[v], dsu_right.tout[v], i); } sort(queries.begin(), queries.end()); FenwickTree fenwick(n); auto move_borders = [&](int& curr_l, int& curr_r, int l, int r) { while (curr_l > l) { --curr_l; int v = dsu_right.vertices[curr_l]; fenwick.update(dsu_left.tin[v], 1); } while (curr_r < r) { ++curr_r; int v = dsu_right.vertices[curr_r]; fenwick.update(dsu_left.tin[v], 1); } while (curr_l < l) { int v = dsu_right.vertices[curr_l]; fenwick.update(dsu_left.tin[v], -1); ++curr_l; } while (curr_r > r) { int v = dsu_right.vertices[curr_r]; fenwick.update(dsu_left.tin[v], -1); --curr_r; } }; int curr_l = 0; int curr_r = -1; for (const auto& [l, r, idx, block] : queries) { move_borders(curr_l, curr_r, l, r); int v = s[idx]; for (int k = dsu_left.max_k - 1; k >= 0; --k) { if (dsu_left.binup[k][v] > ls[idx]) { v = dsu_left.binup[k][v]; } } if (dsu_left.binup[0][v] >= ls[idx]) v = dsu_left.binup[0][v]; if (fenwick.query(dsu_left.tin[v], dsu_left.tout[v]) > 0) { ans[idx] = 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...