Submission #136888

#TimeUsernameProblemLanguageResultExecution timeMemory
136888quotitquotWerewolf (IOI18_werewolf)C++14
0 / 100
496 ms524288 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 = 1e5 + 1; int trmx[4*M]; int trmn[4*M]; vector<int>g[M]; int d[M], a[M], t; void dfs( int v, int p ) { d[v] = t ++; for( auto to: g[v] ) if( to != p ) dfs( to, v ); } void bld( int v, int tl, int tr ) { if( tl == tr ) trmx[v] = trmn[v] = a[tl]; else { int tm = (tl + tr) / 2; bld( v*2, tl, tm ); bld( v*2+1, tm+1, tr ); trmx[v] = max( trmx[v*2], trmx[v*2+1] ); trmn[v] = min( trmn[v*2], trmn[v*2+1] ); } } int get_mx( int v, int tl, int tr, int l, int r ) { if( l > r ) return 0; if( tl == l && tr == r ) return trmx[v]; int tm = (tl + tr) / 2; return max( get_mx( v*2, tl, tm, l, min(tm, r) ), get_mx( v*2+1, tm+1, tr, max(tm+1, l), r ) ); } int get_mn( int v, int tl, int tr, int l, int r ) { if( l > r ) return 1e8; if( tl == l && tr == r ) return trmn[v]; int tm = (tl + tr) / 2; return min( get_mn( v*2, tl, tm, l, min(tm, r) ), get_mn( v*2+1, tm+1, tr, max(tm+1, l), r ) ); } int g_max( int l, int r, int n ) { return get_mx( 1, 0, n-1, l, r ); } int g_min( int l, int r, int n ) { return get_mn( 1, 0, n-1, l, r ); } 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 < Q; i ++ ) { if( g_min( S[i], E[i], N ) >= L[i] && g_max( S[i], E[i], N ) <= R[i] ) { A[i] = 1; continue; } if( g_max( S[i], E[i], N ) <= 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], N ) >= 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, N ) < 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], N ) <= 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...