Submission #208989

#TimeUsernameProblemLanguageResultExecution timeMemory
208989spdskatrWerewolf (IOI18_werewolf)C++14
100 / 100
1688 ms156760 KiB
#include "werewolf.h" #include <cstdio> #include <vector> #include <cstdlib> #include <algorithm> #include <utility> #include <functional> #include <cassert> #define fi first #define se second #define SZ (1<<18) using namespace std; typedef pair<int, pair<int, int>> EDGE; int N, M, Q; vector<int> ans; EDGE edges[400005]; class KRT { int uf[400005], rep[400005], cnt, cnt2; int f(int x) { if (x == uf[x]) return x; return uf[x] = f(uf[x]); } void un(int x, int y) { rep[f(y)] = cnt; uf[f(x)] = f(y); } public: int seq[400005], val[400005], lc[400005], rc[400005], pos[400005], sz[400005]; int jp[400005][20]; int dfs(int x, int rev) { if (x < N) { seq[cnt2] = x; pos[x] = cnt2++; return sz[x]; } jp[lc[x]][0] = jp[rc[x]][0] = x; sz[x] += dfs(lc[x], rev); sz[x] += dfs(rc[x], rev); if (rev) val[x] = min(val[lc[x]], val[rc[x]]); else val[x] = max(val[lc[x]], val[rc[x]]); pos[x] = pos[lc[x]]; return sz[x]; } void reconstruct(int rev) { // Rev set to 1 to toggle maximum spanning tree for (int i = 0; i < N; i++) { val[i] = rep[i] = i; sz[i] = 1; uf[i] = i; } cnt = N; for (int i = 0; i < M; i++) { int u = edges[i].se.fi, v = edges[i].se.se; if (f(u) != f(v)) { lc[cnt] = rep[f(u)]; rc[cnt] = rep[f(v)]; un(u, v); cnt++; } } jp[cnt-1][0] = cnt-1; dfs(cnt-1, rev); for (int b = 1; b < 20; b++) for (int i = 0; i < cnt; i++) { jp[i][b] = jp[jp[i][b-1]][b-1]; } } pair<int, int> find_range(int x, int lim, int rev) { int cur = x; for (int i = 19; i >= 0; i--) { if (rev) { if (val[jp[cur][i]] >= lim) cur = jp[cur][i]; } else { if (val[jp[cur][i]] <= lim) cur = jp[cur][i]; } } return { pos[cur], pos[cur] + sz[cur] - 1 }; } } tree1, tree2; class PersistentSegtree { public: int st[16000000], lc[16000000], rc[16000000], heads[200005], al = 1; void seg_inc(int n, int pn, int lo, int hi, int i) { if (lo + 1 == hi) { st[n] = st[pn] + 1; return; } lc[n] = lc[pn], rc[n] = rc[pn]; int mid = (lo + hi) / 2; if (mid > i) seg_inc(lc[n] = al++, lc[pn], lo, mid, i); else seg_inc(rc[n] = al++, rc[pn], mid, hi, i); st[n] = st[lc[n]] + st[rc[n]]; } int seg_q(int n, int pn, int lo, int hi, int l, int r) { if (lo >= r || hi <= l) return 0; if (lo >= l && hi <= r) return st[n] - st[pn]; int mid = (lo + hi) / 2; return seg_q(lc[n], lc[pn], lo, mid, l, r) + seg_q(rc[n], rc[pn], mid, hi, l, r); } } st; 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) { N = n; M = X.size(); Q = S.size(); for (int i = 0; i < M; i++) { edges[i] = { max(X[i], Y[i]), { X[i], Y[i] } }; } sort(edges, edges+M); tree1.reconstruct(0); // Werewolf tree for (int i = 0; i < M; i++) { edges[i] = { min(X[i], Y[i]), { X[i], Y[i] } }; } sort(edges, edges+M, greater<EDGE>()); tree2.reconstruct(1); // Human tree for (int i = 0; i < N; i++) { st.heads[i] = st.al++; st.seg_inc(st.heads[i], (i == 0 ? 0 : st.heads[i-1]), 0, N, tree2.pos[tree1.seq[i]]); } for (int i = 0; i < Q; i++) { pair<int, int> wolf = tree1.find_range(E[i], R[i], 0); pair<int, int> human = tree2.find_range(S[i], L[i], 1); int res = st.seg_q(st.heads[wolf.se], (wolf.fi == 0 ? 0 : st.heads[wolf.fi-1]), 0, N, human.fi, human.se + 1); ans.push_back(res > 0); } 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...