제출 #155093

#제출 시각아이디문제언어결과실행 시간메모리
155093imyujin늑대인간 (IOI18_werewolf)C++17
0 / 100
1392 ms88764 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; #define rb(x) ((x)&(-(x))) const int MAXN = 200010; int N; int u[MAXN], d[MAXN]; int dot[MAXN]; vector<int> qry[MAXN]; vector<int> ed[MAXN]; int bit[MAXN]; struct TREE { int par[20][MAXN], uni[MAXN]; vector<int> chi[MAXN]; int dfn[MAXN], dfr[MAXN]; int dfs(int x, int d) { dfn[x] = dfr[x] = d; for(auto a : chi[x]) dfr[x] = dfs(a, dfr[x] + 1); return dfr[x]; } int cnttt = 0; int guni(int x) { //if(++cnttt < 100) printf("uni[%d] = %d, %d\n", x, uni[x], ~uni[x]); return ~uni[x] ? uni[x] = guni(uni[x]) : x; } TREE() { memset(par, 0, sizeof(par)); memset(uni, -1, sizeof(uni)); for(int i = N - 1; i >= 0; i--) for(auto a : ed[i]) if(a > i) { //printf("%d\n", a); int x = guni(a); if(x != i) { par[0][x] = uni[x] = i; chi[i].push_back(x); } } for(int i = 1; i < 20; i++) for(int j = 0; j < N; j++) par[i][j] = par[i - 1][par[i - 1][j]]; dfs(0, 1); //for(int i = 0; i < N; i++) printf("%d ", dfn[i]); //printf("\n"); } int gr(int x, int l) { for(int i = 19; i >= 0; i--) if(par[i][x] >= l) x = par[i][x]; return x; } }; void updbit(int x) { for(; x <= N; x += rb(x)) bit[x]++; } int gbit(int x) { int ans = 0; for(; x; x -= rb(x)) ans += bit[x]; return ans; } int gbit(int x, int y) { return gbit(y) - gbit(x - 1); } vector<int> check_validity(int NN, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) { N = NN; int M = X.size(), Q = S.size(); //printf("*\n"); for(int i = 0; i < M; i++) { ed[X[i]].push_back(Y[i]); ed[Y[i]].push_back(X[i]); } TREE hm = TREE(); for(int i = 0; i < N; i++) ed[i].clear(); for(int i = 0; i < M; i++) { ed[N - X[i] - 1].push_back(N - Y[i] - 1); ed[N - Y[i] - 1].push_back(N - X[i] - 1); } TREE ww = TREE(); for(int i = 0; i < N; i++) dot[hm.dfn[i]] = ww.dfn[N - i - 1]; //for(int i = 1; i <= N; i++) printf("%d ", dot[i]); for(int i = 0; i < Q; i++) { int t = hm.gr(S[i], L[i]); qry[hm.dfn[t] - 1].push_back(- i - 1); qry[hm.dfr[t]].push_back(i); t = ww.gr(N - E[i] - 1, N - R[i] - 1); u[i] = hm.dfr[t]; d[i] = hm.dfn[t]; } vector<int> ans(Q); for(int i = 0; i <= N; i++) { if(i) updbit(dot[i]); for(auto a : qry[i]) { if(a >= 0) ans[a] += gbit(d[a], u[a]); else ans[-a - 1] -= gbit(d[-a - 1], u[-a - 1]); } } for(auto &a : ans) a = min(a,1); return ans; //return X; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...