Submission #114709

#TimeUsernameProblemLanguageResultExecution timeMemory
114709WhipppedCreamWerewolf (IOI18_werewolf)C++17
0 / 100
353 ms92016 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("O3") #pragma GCC target ("sse4") using namespace std; #define X first #define Y second #define pb push_back typedef pair<int, int> ii; typedef long long ll; typedef vector<int> vi; const int maxn = 2e5+5; struct dsu { vector<int> par; dsu(int n = 0) { par.resize(n); for(int i = 0; i< n; i++) par[i] = i; } int findset(int x) { if(x == par[x]) return x; return par[x] = findset(par[x]); } }; dsu hum, wolf; int n, m, q; vector<int> adj[maxn]; struct tahm { int s, e, l, r, id; int hum, wolf; tahm(int s, int e, int l, int r, int id): s(s), e(e), l(l), r(r), id(id) {} }; bool cmpl(tahm a, tahm b) { return a.l< b.l; } bool cmpr(tahm a, tahm b) { return a.r< b.r; } vector<tahm> kench; vector<int> twolf[maxn]; vector<int> thum[maxn]; vector<int> pred; int numb[maxn]; int lb[maxn]; int rb[maxn]; void dfs(int u = 2*n-2) { if(u< n) pred.pb(u); for(int v : twolf[u]) dfs(v); } void calc(int u = 2*n-2) { lb[u] = 1e9, rb[u] = -1; if(u< n) lb[u] = rb[u] = numb[u]; for(int v : twolf[u]) { calc(v); lb[u] = min(lb[u], lb[v]); rb[u] = max(rb[u], rb[v]); } // printf("lb[%d] = %d, rb[%d] = %d\n", u, lb[u], u, rb[u]); } struct node { int val; node *left, *right; node(int _val, node* _left, node *_right) { val = _val; left = _left; right = _right; } node* insert(int x, int L = 0, int R = n-1) { if(L<= x && x<= R) { if(L == R) return new node(val+1, NULL, NULL); int M = (L+R)/2; return new node(val+1, left->insert(x, L, M), right->insert(x, M+1, R)); } return this; } int ask(int i, int j, int L = 0, int R = n-1) { if(i> R || j< L) return 0; if(i<= L && R<= j) return val; int M = (L+R)/2; int x = left->ask(i, j, L, M); int y = right->ask(i, j, M+1, R); return x+y; } }; node* zero = new node(0, NULL, NULL); node* roots[maxn]; vector<int> elems[maxn]; void comb(int u = 2*n-2) { if(u< n) { elems[u].pb(numb[u]); roots[u] = zero->insert(numb[u]); return; } ii big = {0, -1}; for(int v : thum[u]) { comb(v); big = max(big, ii((int) elems[v].size(), v)); } swap(elems[u], elems[big.Y]); roots[u] = roots[big.Y]; for(int v : thum[u]) { for(int x : elems[v]) { roots[u] = roots[u]->insert(x); } } } vector<int> check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) { n = N; m = X.size(); q = S.size(); for(int i = 0; i< q; i++) kench.pb(tahm(S[i], E[i], L[i], R[i], i)); for(int i = 0; i< m; i++) { adj[X[i]].pb(Y[i]); adj[Y[i]].pb(X[i]); } wolf = dsu(2*n); sort(kench.begin(), kench.end(), cmpr); int pt = 0; int cnt = n; for(int i = 0; i< n; i++) { for(int v : adj[i]) { if(v< i) { int a = wolf.findset(i); int b = wolf.findset(v); if(a == b) continue; wolf.par[a] = wolf.par[b] = cnt; twolf[cnt].pb(a); twolf[cnt].pb(b); // printf("%d-->%d %d-->%d\n", cnt, a, cnt, b); cnt++; } } while(pt< q && kench[pt].r == i) { int e = kench[pt].e; int pp = wolf.findset(e); kench[pt].wolf = pp; pt++; } } // printf("finished wolf\n"); hum = dsu(2*n); sort(kench.begin(), kench.end(), cmpl); reverse(kench.begin(), kench.end()); pt = 0; cnt = n; for(int i = n-1; i>= 0; i--) { for(int v : adj[i]) { if(v> i) { int a = hum.findset(v); int b = hum.findset(i); if(a == b) continue; hum.par[a] = hum.par[b] = cnt; // printf("%d->%d, %d->%d\n", cnt, a, cnt, b); thum[cnt].pb(a); thum[cnt].pb(b); cnt++; } } while(pt< q && kench[pt].l == i) { int s = kench[pt].s; int pp = hum.findset(s); kench[pt].hum = pp; pt++; } } dfs(); // for(int i = 0; i< n; i++) printf("%d ", pred[i]); // printf("\n"); for(int i = 0; i< n; i++) numb[pred[i]] = i; calc(); // printf("finished renumbering\n"); zero->left = zero->right = zero; comb(); vector<int> ans(q); for(int i = 0; i< q; i++) { int wolf = kench[i].wolf, hum = kench[i].hum; int id = kench[i].id; int lo = lb[wolf], hi = rb[wolf]; // if(hum == 5) printf("wolf is %d [%d %d] ans is %d\n", wolf, lo, hi, roots[hum]->ask(0, 0)); int res = roots[hum]->ask(lo, hi); ans[id] = 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...