제출 #222771

#제출 시각아이디문제언어결과실행 시간메모리
222771rama_pang늑대인간 (IOI18_werewolf)C++14
100 / 100
1333 ms127256 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; // Disjoint Set vector<int> disj; int Find(int x) { return disj[x] == x ? x : disj[x] = Find(disj[x]); } class BIT { private: int sz; vector<int> tree; void Update_(int p, int x) { for (int i = p + 1; i <= sz; i += (i & -i)) { tree[i - 1] += x; } } int Query_(int p) { int res = 0; for (int i = p + 1; i > 0; i -= (i & -i)) { res += tree[i - 1]; } return res; } public: BIT() {} BIT(int n) : sz(n) { tree.assign(sz, 0); } void Update(int p, int x) { return Update_(p, x); } int Query(int L, int R) { return Query_(R) - Query_(L - 1); } }; // Line Sweep struct Event { int type; // 0 (point), 1 (query end), -1 (query start) int lo, hi; int id; Event() {} Event(int t, int l, int h, int i) : type(t), lo(l), hi(h), id(i) {} bool operator < (const Event &o) const { return type < o.type; } }; vector<vector<Event>> events; void AddPoint(int x, int y) { events[x].emplace_back(0, y, y, -1); } void AddQuery(int x_1, int x_2, int y_1, int y_2) { static int id_ = 0; events[x_1].emplace_back(-1, y_1, y_2, id_); events[x_2].emplace_back(+1, y_1, y_2, id_); id_++; } void LineSweep(int n, vector<int> &InsideRectangle) { BIT tree(n); for (int x = 0; x < n; x++) { sort(begin(events[x]), end(events[x])); for (auto e : events[x]) { if (e.type == 0) { // Add Point tree.Update(e.lo, +1); } else { // Process Query InsideRectangle[e.id] += e.type * tree.Query(e.lo, e.hi); } } } } vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) { disj.resize(N), events.resize(2 * N); vector<vector<int>> adj(N); for (int i = 0; i < (int) X.size(); i++) { adj[X[i]].emplace_back(Y[i]); adj[Y[i]].emplace_back(X[i]); } vector<int> LineL, LineR; vector<vector<int>> AncL(N, vector<int>(20, -1)), AncR(N, vector<int>(20, -1)); function<void(int, vector<vector<int>>&, vector<vector<int>>&, vector<int>&)> dfs = [&]( int n, vector<vector<int>> &adjList, vector<vector<int>> &anc, vector<int> &v) { v.emplace_back(n); for (int j = 1; j < 20; j++) { if (anc[n][j - 1] != -1) { anc[n][j] = anc[anc[n][j - 1]][j - 1]; } } for (auto i : adjList[n]) { anc[i][0] = n; dfs(i, adjList, anc, v); } v.emplace_back(n); }; { // Created rooted tree for L (low-population restricted) iota(begin(disj), end(disj), 0); vector<vector<int>> tree(N); for (int u = N - 1; u >= 0; u--) { for (auto v : adj[u]) { if (v < u) continue; if (u == Find(v)) continue; tree[u].emplace_back(Find(v)); disj[Find(v)] = u; } } AncL[0][0] = -1; dfs(0, tree, AncL, LineL); } { // Created rooted tree for R (high-population restricted) iota(begin(disj), end(disj), 0); vector<vector<int>> tree(N); for (int u = 0; u < N; u++) { for (auto v : adj[u]) { if (v > u) continue; if (u == Find(v)) continue; tree[u].emplace_back(Find(v)); disj[Find(v)] = u; } } AncR[N - 1][0] = -1; dfs(N - 1, tree, AncR, LineR); } vector<pair<int, int>> posL(N, {-1, -1}), posR(N, {-1, -1}); for (int i = 0; i < 2 * N; i++) { if (posL[LineL[i]].first == -1) { posL[LineL[i]].first = i; } else { posL[LineL[i]].second = i; } if (posR[LineR[i]].first == -1) { posR[LineR[i]].first = i; } else { posR[LineR[i]].second = i; } } for (int i = 0; i < N; i++) { AddPoint(posL[i].first, posR[i].first); } int Q = L.size(); for (int i = 0; i < Q; i++) { int s = S[i]; int e = E[i]; for (int j = 19; j >= 0; j--) { if (AncL[s][j] != -1 && AncL[s][j] >= L[i]) s = AncL[s][j]; if (AncR[e][j] != -1 && AncR[e][j] <= R[i]) e = AncR[e][j]; } AddQuery(posL[s].first, posL[s].second, posR[e].first, posR[e].second); } vector<int> res(Q, 0); LineSweep(2 * N, res); for (int i = 0; i < Q; i++) res[i] = res[i] > 0; return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...