| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 287330 | infinite_iq | Werewolf (IOI18_werewolf) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std ;
#define mid (l+r)/2
#define le node*2
#define ri node*2+1
#define pb push_back
#define C continue
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define all(x) x.begin(), x.end()
typedef vector < int > vi ;
#include "werewolf.h"
int n , m , q ;
vi v [200009] , ans ;
int a [200009] , pos [200009] ;
int stop [200009][2][2] ;
void dfs ( int node , int p , int ord ) {
a [ord] = node ;
for ( auto u : v [node] ) {
if ( u == p ) C ;
dfs ( u , node , ord + 1 ) ;
}
vi 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 < m ; i ++ ) {
int a = X [i] , b = Y [i] ;
v [a] .pb ( b ) ;
v [b] .pb ( a ) ;
}
for ( int i = 0 ; i < n ; i ++ ) {
if ( v [i] .size () == 1 ) {
dfs ( i , i , 0 ) ;
break ;
}
}
set < int > s ;
for ( int i = 0 ; i < n ; i ++ ) {
pos [ a [i] ] = i ;
v [i] .clear () ;
s .ins ( i ) ;
}
for ( int i = 0 ; i < q ; i ++ ) {
v [ R [i] ] .pb ( i ) ;
swap ( S [i] , E [i] ) ;
}
for ( int i = 0 ; i < n ; i ++ ) {
s .era ( pos [i] ) ;
for ( auto u : v [i] ) {
int l = pos[S [u]] , r = pos [E [u]] , id = u ;
if ( l > r ) swap ( l , r ) ;
auto it = s .lb ( l ) ;
stop [id][0][0] = ( it == s.end () ? r : min ( (int)(*it -1) , r ) ) ;
it = s .ub ( r ) ;
stop [id][0][1] = ( it == s.begin () ? l : max ( (int)(*(--it) + 1) , l ) ) ;
}
}
for ( int i = 0 ; i < n ; i ++ ) {
v [i] .clear () ;
s .ins ( i ) ;
}
for ( int i = 0 ; i < q ; i ++ ) {
v [ L [i] ] .pb ( i ) ;
}
for ( int i = n - 1 ; i >= 0 ; i -- ) {
s .era ( pos [i] ) ;
for ( auto u : v [i] ) {
int l = pos [S [u]] , r = pos [E [u]] , id = u ;
if ( l > r ) swap ( l , r ) ;
auto it = s .lb ( l ) ;
stop [id][1][0] = ( it == s.end () ? r : min ( (int)(*it -1) , r ) ) ;
it = s .ub ( r ) ;
stop [id][1][1] = ( it == s.begin () ? l : max ( (int)(*(--it) + 1) , l ) ) ;
}
}
for ( int i = 0 ; i < q ; i ++ ) {
int st = pos [S [i]] , en = pos [E [i]] ;
if ( st <= en ) {
int bound1 = stop [i][0][0] ;
int bound2 = stop [i][1][1] ;
if ( bound1 < st || bound2 > en || bound1 < bound2 ) {
ans .pb ( 0 ) ;
C ;
}
int l = bound2 , r = bound1 ;
ans .pb ( 1 ) ;
}
else {
int bound1 = stop [i][0][1] ;
int bound2 = stop [i][1][0] ;
if ( bound1 > st || bound2 < en || bound2 < bound1 ) {
ans .pb ( 0 ) ;
C ;
}
int l = bound1 , r = bound2 ;
ans .pb ( 1 ) ;
}
}
return ans ;
}