제출 #1125240

#제출 시각아이디문제언어결과실행 시간메모리
1125240Pekiban늑대인간 (IOI18_werewolf)C++20
0 / 100
864 ms139000 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; #define pb push_back const int N = 4e5 + 5, LOG = 19, SQ = 500; struct krt { vector<int> g[N]; int a[N], p[N], W[N], tin[N], tout[N], up[LOG][N], D[N], C, tm; bool fl = 0; // fl = 1 za MX, 0 za MN void init(int n) { C = n-1; iota(p, p+N, 0); iota(W, W+N, 0); } int get(int x) { if (x == p[x]) return x; return p[x] = get(p[x]); } bool unite(int u, int v) { u = get(u), v = get(v); if (u == v) return 0; p[u] = p[v] = ++C; W[C] = (fl ? min(W[u], W[v]) : max(W[u], W[v])); g[C].pb(u); g[C].pb(v); g[u].pb(C); g[v].pb(C); return 1; } void dfs(int s, int e = -1) { tin[s] = ++tm; a[tm] = s; for (auto u : g[s]) { if (u == e) continue; D[u] = D[s] + 1, up[0][u] = s; dfs(u, s); } tout[s] = tm; } void init2() { dfs(C); for (int i = 1; i < LOG; ++i) { for (int j = 1; j <= C; ++j) up[i][j] = up[i-1][up[i-1][j]]; } } int F(int s, int l, int r) { for (int i = LOG-1; i >= 0; --i) { if (up[i][s] && l <= W[up[i][s]] && W[up[i][s]] <= r) s = up[i][s]; } return s; } } MN, MX; struct bit { int b[N]; void add(int p, int x) { for (; p < N; p |= (p + 1)) b[p] += x; } int sum(int r) { int S = 0; for (; r >= 0; r = (r & (r + 1)) - 1) S += b[r]; return S; } int sum(int l, int r) { return sum(r) - sum(l - 1); } } T; bool cmp(array<int, 4> &A, array<int, 4> &B) { if (A[0] / SQ != B[0] / SQ) return A[0] / SQ < B[0] / SQ; return A[1] < B[1]; } bool cmp1(array<int, 2> &A, array<int, 2> &B) { return max(A[0], A[1]) < max(B[0], B[1]); } bool cmp2(array<int, 2> &A, array<int, 2> &B) { return min(A[0], A[1]) > min(B[0], B[1]); } vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) { MN.init(n); MX.init(n); MN.fl = 0, MX.fl = 1; int q = S.size(), m = X.size(); array<int, 2> e[m]; for (int i = 0; i < m; ++i) e[i] = {X[i], Y[i]}; sort(e, e+m, cmp1); for (int i = 0; i < m; ++i) MN.unite(e[i][0], e[i][1]); sort(e, e+m, cmp2); for (int i = 0; i < m; ++i) MX.unite(e[i][0], e[i][1]); MX.init2(); MN.init2(); array<int, 4> qu[q]; for (int i = 0; i < q; ++i) { int x = MX.F(S[i], L[i], n-1); qu[i] = {MX.tin[x], MX.tout[x], E[i], i}; int y = MN.F(E[i], 0, R[i]); } sort(qu, qu + q, cmp); int r = -1, l = 0; vector<int> ans(q); for (int i = 0; i < q; ++i) { while (r > qu[i][1]) { if (MX.a[r] < n) T.add(MN.tin[MX.a[r]], -1); --r; } while (r < qu[i][1]) { ++r; if (MX.a[r] < n) T.add(MN.tin[MX.a[r]], 1); } while (l > qu[i][0]) { --l; if (MX.a[l] < n) T.add(MN.tin[MX.a[l]], 1); } while (l < qu[i][0]) { if (MX.a[l] < n) T.add(MN.tin[MX.a[l]], -1); ++l; } int x = MN.F(qu[i][2], 0, R[qu[i][3]]); ans[qu[i][3]] = T.sum(MN.tin[x], MN.tout[x]) > 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...