제출 #159333

#제출 시각아이디문제언어결과실행 시간메모리
159333iefnah06늑대인간 (IOI18_werewolf)C++11
100 / 100
1322 ms155152 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; using ll = long long; const int MAXN = 200010; int N, M, Q; vector<int> adj[MAXN]; int par[MAXN]; const int MAXL = 20; int anc[2][MAXL][MAXN]; vector<int> tr[MAXN]; void reset() { fill_n(par, N, -1); for (int i = 0; i < N; i++) tr[i].clear(); } int getpar(int a) { return par[a] == -1 ? a : par[a] = getpar(par[a]); } int st[MAXN], ed[MAXN]; int ind; void dfs(int cur = 0) { st[cur] = ind++; for (int nxt : tr[cur]) { dfs(nxt); } ed[cur] = ind; } const int MAXQ = 200010; vector<int> queries[MAXN]; int ql[MAXQ], qr[MAXQ]; vector<int> ans; struct seg { seg* ch[2] = {nullptr, nullptr}; }; void update(int p, seg* &n, int x = 0, int y = N) { if (!n) { n = new seg(); } if (y - x > 1) { int z = (x + y) / 2; if (p < z) { update(p, n->ch[0], x, z); } else { update(p, n->ch[1], z, y); } } } int query(int l, int r, seg* n, int x = 0, int y = N) { if (!n) { return 0; } if (l <= x && y <= r) { return 1; } else { int z = (x + y) / 2; if (l < z && query(l, r, n->ch[0], x, z)) return 1; if (z < r && query(l, r, n->ch[1], z, y)) return 1; return 0; } } seg* merge(seg* a, seg* b) { if (!a) return b; if (!b) return a; a->ch[0] = merge(a->ch[0], b->ch[0]); a->ch[1] = merge(a->ch[1], b->ch[1]); return a; } seg* roots[MAXN]; void go(int cur = N - 1) { for (int nxt : tr[cur]) { go(nxt); roots[cur] = merge(roots[cur], roots[nxt]); } update(st[cur], roots[cur]); for (int q : queries[cur]) { ans[q] = query(ql[q], qr[q], roots[cur]); } } 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 = int(X.size()); Q = int(S.size()); for (int i = 0; i < M; i++) { adj[X[i]].push_back(Y[i]); adj[Y[i]].push_back(X[i]); } reset(); for (int a = N - 1; a >= 0; a--) { for (int b : adj[a]) { if (b < a) continue; int t = getpar(b); if (a != t) { par[t] = a; anc[0][0][t] = a; tr[a].push_back(t); } } } anc[0][0][0] = -1; dfs(); reset(); for (int a = 0; a < N; a++) { for (int b : adj[a]) { if (b > a) continue; int t = getpar(b); if (a != t) { par[t] = a; anc[1][0][t] = a; tr[a].push_back(t); } } } anc[1][0][N - 1] = -1; for (int t = 0; t < 2; t++) { for (int l = 1; l < MAXL; l++) { for (int i = 0; i < N; i++) { if (anc[t][l - 1][i] == -1) { anc[t][l][i] = -1; } else { anc[t][l][i] = anc[t][l - 1][anc[t][l - 1][i]]; } } } } for (int q = 0; q < Q; q++) { int a = S[q], b = E[q]; for (int l = MAXL - 1; l >= 0; l--) { if (anc[0][l][a] != -1 && anc[0][l][a] >= L[q]) { a = anc[0][l][a]; } } for (int l = MAXL - 1; l >= 0; l--) { if (anc[1][l][b] != -1 && anc[1][l][b] <= R[q]) { b = anc[1][l][b]; } } ql[q] = st[a]; qr[q] = ed[a]; queries[b].push_back(q); } ans = vector<int>(Q); go(); 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...