제출 #136886

#제출 시각아이디문제언어결과실행 시간메모리
136886quotitquot늑대인간 (IOI18_werewolf)C++14
0 / 100
477 ms524292 KiB
#include "werewolf.h" #include<bits/stdc++.h> #define ll long long #define fr fisrt #define se second #define pb push_back using namespace std; const ll M = 22; const ll N_M = 4e5 + 1; int mx[N_M][M]; int mn[N_M][M]; vector<int>g[N_M]; int d[N_M], a[N_M], s[N_M], t; void dfs( int v, int p ) { d[v] = t ++; for( auto to: g[v] ) if( to != p ) dfs( to, v ); } int g_max( int l, int r ) { int m = d[r-l+1]; int mi = r - (1 << m) + 1; return max( mx[l][m], mx[mi][m] ); } int g_min( int l, int r ) { int m = d[r-l+1]; int mi = r - (1 << m) + 1; return min( mn[l][m], mn[mi][m] ); } 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(); vector<int> A(Q); for( int i = 0; i < int(X.size()); i ++ ) { g[X[i]].pb( Y[i] ); g[Y[i]].pb( X[i] ); } int st = 0; for( int i = 0; i < N; i ++ ) if( int(g[i].size()) == 1 ) st = i; dfs( st, st ); for( int i = 0; i < N; i ++ ) a[d[i]] = i; for( int i = 0; i < Q; i ++ ) { S[i] = d[S[i]]; E[i] = d[E[i]]; if( S[i] > E[i] ) swap( S[i], E[i] ); } for( int i = 0; i < M; i ++ ) { int h = (1 << i); if( h >= N ) break; s[h] = 1; } for( int i = 1; i < N; i ++ ) s[i] += s[i-1]; for( int i = 0; i < N; i ++ ) mx[i][0] = mn[i][0] = a[i]; for( int i = 0; i < N; i ++ ) { for( int j = 1; j < M; j ++ ) { int h1 = (1 << j); int h2 = (1 << (j-1)); if( i+h1-1 >= N ) break; mx[i][j] = max( mx[i][j-1], mx[i+h2][j-1] ); mn[i][j] = min( mn[i][j-1], mn[i+h2][j-1] ); } } for( int i = 0; i < Q; i ++ ) { if( g_min( S[i], E[i] ) >= L[i] && g_max( S[i], E[i] ) <= R[i] ) { A[i] = 1; continue; } if( g_max( S[i], E[i] ) <= R[i] ) { if( a[S[i]] >= L[i] && a[S[i]] <= R[i] ) A[i] = 1; else A[i] = 0; continue; } if( g_min( S[i], E[i] ) >= L[i] ) { if( a[E[i]] >= L[i] && a[E[i]] <= R[i] ) A[i] = 1; else A[i] = 0; continue; } int l = S[i], r = E[i], m; while( l < r ) { m = (l + r) / 2; if( g_min( S[i], m ) < L[i] ) r = m; else l = m + 1; } if( l == S[i] ) { A[i] = 0; continue; } if( a[l-1] < L[i] or a[i-1] > R[i] ) { A[i] = 0; continue; } if( l == E[i] ) { A[i] = 1; continue; } A[i] = g_max( l+1, E[i] ) <= R[i]; } return A; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...