제출 #293316

#제출 시각아이디문제언어결과실행 시간메모리
293316Atill83늑대인간 (IOI18_werewolf)C++14
100 / 100
1253 ms124588 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; typedef vector<int> vi; const int MAXN = (int) 5e5 + 5; int n; int t[MAXN]; void upd(int v, int val){ for(; v < MAXN; v += (v&-v)) t[v] += val; } int gt(int l, int r){ l--; int res = 0; for(; r; r -= (r&-r)) res += t[r]; for(; l; l -= (l&-l)) res -= t[l]; return res; } vector<pair<int, int>> Qs[MAXN]; vector<int> A; struct ali{ int cev[MAXN], tin[MAXN], tout[MAXN], sz[MAXN], pari[MAXN][22]; int cur = 1; int par[MAXN]; vector<int> adj[MAXN]; void ini(){ for(int i = 0; i < n; i++){ adj[i].clear(); sz[i] = 1; par[i] = i; pari[i][0] = i; } } int find_set(int v){ if(par[v] == v) return v; return par[v] = find_set(par[v]); } void merge(int a, int b, bool cr){ a = find_set(a); b = find_set(b); if(a == b) return; if(cr){ if(a < b) swap(a, b); sz[a] += sz[b]; par[b] = a; pari[b][0] = a; adj[a].push_back(b); }else{ if(a > b) swap(a, b); sz[a] += sz[b]; par[b] = a; pari[b][0] = a; adj[a].push_back(b); } } void dfs(int v){ tin[v] = cur++; cev[cur - 1] = v; for(int l = 1; l < 22; l++) pari[v][l] = pari[pari[v][l - 1]][l - 1]; for(int j: adj[v]) dfs(j); tout[v] = cur - 1; } void dfs2(int v, bool keep, ali &s){ int hv = -1; for(int j: adj[v]) if(hv == -1 || sz[j] > sz[hv]) hv = j; for(int j: adj[v]) if(j != hv) dfs2(j, 0, s); if(hv != -1) dfs2(hv, 1, s); for(int j: adj[v]) if(j != hv) for(int i = tin[j]; i <= tout[j]; i++) upd(s.tin[cev[i]], 1); upd(s.tin[v], 1); for(auto j: Qs[v]){ int rs = gt(s.tin[j.first], s.tout[j.first]); assert(rs >= 0); A[j.second] = (rs != 0); } if(keep == 0) for(int i = tin[v]; i <= tout[v]; i++) upd(s.tin[cev[i]], -1); } } st1, st2; vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) { n = N; int M = X.size(), Q = S.size(); st1.ini(); st2.ini(); A.resize(Q); vector<int> esi; for(int i = 0; i < M; i++){ esi.push_back(i); } sort(esi.begin(), esi.end(), [&X, &Y](int a, int b){ if(min(X[a], Y[a]) == min(X[b], Y[b])){ return max(X[a], Y[a]) < max(X[b], Y[b]); } return min(X[a], Y[a]) > min(X[b], Y[b]); }); st1.ini(); st2.ini(); for(int i = 0; i < M; i++){ st1.merge(X[esi[i]], Y[esi[i]], 0); } sort(esi.begin(), esi.end(), [&X, &Y](int a, int b){ if(max(X[a], Y[a]) == max(X[b], Y[b])) return min(X[a], Y[a]) > min(X[b], Y[b]); return max(X[a], Y[a]) < max(X[b], Y[b]); }); for(int i = 0; i < M; i++){ st2.merge(X[esi[i]], Y[esi[i]], 1); } st1.dfs(0); st2.dfs(n - 1); for(int i = 0; i < Q; i++){ for(int j = 21; j >= 0; j--){ if(st1.pari[S[i]][j] >= L[i]){ S[i] = st1.pari[S[i]][j]; } } for(int j = 21; j >= 0; j--){ if(st2.pari[E[i]][j] <= R[i]){ E[i] = st2.pari[E[i]][j]; } } Qs[S[i]].push_back({E[i], i}); } st1.dfs2(0, 1, st2); return A; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...