Submission #439898

#TimeUsernameProblemLanguageResultExecution timeMemory
439898dxz05Werewolf (IOI18_werewolf)C++14
49 / 100
1883 ms98512 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; const int MAXN = 4e5 + 3e2; #define MP make_pair #define PII pair<int, int> vector<int> g[MAXN]; bool used[MAXN]; int tin[MAXN]; vector<int> vec = {0}; void dfs(int v){ used[v] = true; tin[v] = vec.size(); vec.push_back(v); for (int u : g[v]){ if (!used[u]){ dfs(u); } } } PII t[MAXN][20]; int Log[MAXN]; PII combine(PII lf, PII rg){ return MP(min(lf.first, rg.first), max(lf.second, rg.second)); } void build(int n){ Log[1] = 0; for (int i = 2; i <= n; i++) Log[i] = Log[i / 2] + 1; for (int i = 0; i < 20; i++){ for (int j = 1; j <= n; j++){ if (i == 0){ t[j][i] = MP(vec[j], vec[j]); } else { if (j + (1 << (i - 1)) < MAXN) t[j][i] = combine(t[j][i - 1], t[j + (1 << (i - 1))][i - 1]); } } } } PII get(int l, int r){ if (l > r) return MP(1e9, -1e9); if (l == r) return t[l][0]; int x = Log[r - l + 1]; PII res = combine(t[l][x], t[r - (1 << x) + 1][x]); return res; } PII get_positions(int X, int N, int L, int R){ X = tin[X]; int lf = X, rg = X; int l = 1, r = X; while (l <= r){ int m = (l + r) >> 1; PII f = get(m, X); if (f.first >= L && f.second <= R){ lf = m; r = m - 1; } else l = m + 1; } l = X, r = N; while (l <= r){ int m = (l + r) >> 1; PII f = get(X, m); if (f.first >= L && f.second <= R){ rg = m; l = m + 1; } else r = m - 1; } return MP(lf, rg); } int smaller[MAXN]; int fw[MAXN]; void add(int x, int y){ while (x < MAXN){ fw[x] += y; x += (-x & x); } } int get(int x){ int ret = 0; while (x > 0){ ret += fw[x]; x -= (-x & x); } return ret; } vector<pair<PII, PII>> queries[MAXN]; void dfs2(int v, int l, int r, vector<bool> &used){ used[v] = true; for (int u : g[v]){ if (!used[u] && l <= u && u <= r){ dfs2(u, l, r, used); } } } vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) { int Q = S.size(), M = X.size(); vector<int> A(Q, 0); for (int i = 0; i < M; i++){ g[X[i]].push_back(Y[i]); g[Y[i]].push_back(X[i]); } if (N <= 3000 && M <= 6000 && Q <= 3000){ for (int i = 0; i < Q; i++){ vector<bool> used1(N, false), used2(N, false); dfs2(S[i], L[i], N - 1, used1); dfs2(E[i], 0, R[i], used2); for (int j = L[i]; j <= R[i]; j++){ if (used1[j] && used2[j]) A[i] = 1; } } return A; } for (int i = 0; i < N; i++){ if (g[i].size() == 1){ dfs(i); break; } } build(N); for (int i = 0; i < Q; i++){ PII fs = get_positions(S[i], N, L[i], N - 1), fe = get_positions(E[i], N, 0, R[i]); int l1 = fs.first, r1 = fs.second, l2 = fe.first, r2 = fe.second; //cout << "\t" << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << endl; int l = max(l1, l2), r = min(r1, r2); if (L[i]) queries[L[i] - 1].emplace_back(MP(i, 0), MP(l, r)); queries[R[i]].emplace_back(MP(i, 1), MP(l, r)); } //return A; for (int i = 0; i < N; i++){ add(tin[i], 1); for (auto qu : queries[i]){ int ind = qu.first.first, ty = qu.first.second, l = qu.second.first, r = qu.second.second; // cout << i << ' ' << l << ' ' << r << endl; int res = get(r) - get(l - 1); if (ty == 0) A[ind] -= res; else A[ind] += res; } } for (int i = 0; i < Q; i++) A[i] = A[i] > 0; return A; } /** 6 6 3 5 1 1 2 1 3 3 4 3 0 5 2 4 2 1 2 4 2 2 2 5 4 3 4 6 5 1 2 0 0 1 3 5 1 3 5 4 1 4 0 4 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...