Submission #1003226

#TimeUsernameProblemLanguageResultExecution timeMemory
1003226peraWerewolf (IOI18_werewolf)C++17
100 / 100
738 ms142844 KiB
#include<bits/stdc++.h> #include "werewolf.h" using namespace std; const int NMAX = 2e5 + 1 , LOG = 20; int T = 0; vector<int> ri(NMAX) , rd(NMAX) , ini(NMAX) , outi(NMAX) , ind(NMAX) , outd(NMAX) , t(4 * NMAX) , ord = {0}; vector<vector<int>> p(NMAX , vector<int>(2)) , g(NMAX) , gi(NMAX) , gd(NMAX); vector<vector<vector<int>>> up(2 , vector<vector<int>>(NMAX , vector<int>(LOG))) , queries(NMAX); void update(int u , int l , int r , int pos , int x){ if(l == r){ t[u] = x; return; } int m = (l + r) / 2; if(pos <= m){ update(u * 2 , l , m , pos , x); }else{ update(u * 2 + 1 , m + 1 , r , pos , x); } t[u] = max(t[u * 2] , t[u * 2 + 1]); } int get(int u , int l , int r , int L , int R){ if(l > r || r < L || l > R){ return 0; } if(L <= l && r <= R){ return t[u]; } int m = (l + r) / 2; return max(get(u * 2 , l , m , L , R) , get(u * 2 + 1 , m + 1 , r , L , R)); } int find(int u , int type){ return p[u][type] == u ? p[u][type] : p[u][type] = find(p[u][type] , type); } void unite(int u , int v , int type){ int root_u = find(u , type) , root_v = find(v , type); if(root_u != root_v){ p[root_v][type] = root_u; type == 0 ? ri[root_v] = u : rd[root_v] = u; } } void dfsi(int u){ ini[u] = ++T; for(int x : gi[u]){ dfsi(x); } outi[u] = T; } void dfsd(int u){ ord.push_back(u); ind[u] = ++T; for(int x : gd[u]){ dfsd(x); } outd[u] = T; } int max_up_L(int u , int val){ for(int bit = LOG - 1;bit >= 0;bit--){ if(up[1][u][bit] >= val){ u = up[1][u][bit]; } } return u; } int max_up_R(int u , int val){ for(int bit = LOG - 1;bit >= 0;bit --){ if(up[0][u][bit] <= val){ u = up[0][u][bit]; } } return u; } 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 M = (int)X.size(); for(int i = 0;i < M;i ++){ g[++X[i]].push_back(++Y[i]); g[Y[i]].push_back(X[i]); } for(int i = 1;i <= N;i ++){ for(int x = 0;x < 2;x ++){ p[i][x] = i; } ri[i] = rd[i] = i; } for(int i = 1;i <= N;i ++){ for(int x : g[i]){ if(x < i){ unite(i , x , 0); } } } for(int i = N;i >= 1;i --){ for(int x : g[i]){ if(x > i){ unite(i , x , 1); } } } for(int i = 1;i <= N;i ++){ up[0][i][0] = ri[i]; up[1][i][0] = rd[i]; if(ri[i] != i){ gi[ri[i]].push_back(i); } if(rd[i] != i){ gd[rd[i]].push_back(i); } } dfsi(N); T = 0; dfsd(1); for(int bit = 1;bit < LOG;bit ++){ for(int i = 1;i <= N;i ++){ for(int x = 0;x < 2;x ++){ up[x][i][bit] = up[x][up[x][i][bit - 1]][bit - 1]; } } } int Q = (int)S.size(); vector<int> ans(Q); for(int i = 0;i < Q;i ++){ int root_S = max_up_L(++S[i] , ++L[i]); int root_E = max_up_R(++E[i] , ++R[i]); queries[outd[root_S]].push_back({ind[root_S] , ini[root_E] , outi[root_E] , i}); } for(int i = 1;i <= N;i ++){ update(1 , 1 , N , ini[ord[i]] , i); for(auto x : queries[i]){ ans[x[3]] = get(1 , 1 , N , x[1] , x[2]) >= 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...