제출 #287311

#제출 시각아이디문제언어결과실행 시간메모리
287311infinite_iq늑대인간 (IOI18_werewolf)C++14
34 / 100
1448 ms524288 KiB
#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] , tree [800009] , 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 ) ; } } void build ( int node , int l , int r ) { if ( l == r ) { tree [node] .pb ( a [l] ) ; return ; } build ( le , l , mid ) ; build ( ri , mid + 1 ,r ) ; for ( auto u : tree [le] ) tree [node] .pb ( u ) ; for ( auto u : tree [ri] ) tree [node] .pb ( u ) ; sort ( all ( tree [node] ) ) ; } int query ( int node , int l , int r , int s , int e , int x ) { if ( s > r || e < l ) return 1e9 ; if ( s <= l && e >= r ) { auto it = lb ( tree [node] .begin () , tree [node] .end () , x ) - tree [node] .begin () ; if ( it == tree [node] .size () ) return 1e9 ; return tree [node][it] ; } return min ( query ( le , l , mid , s , e , x ) , query ( ri , mid + 1 , r , s , e , x ) ) ; } 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 ; } } build ( 1 , 0 , n -1 ) ; 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 ( ( query ( 1 , 0 , n-1 , l , r , L [i] ) <= R [i] ) ) ; } 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 ( ( query ( 1 , 0 , n-1 , l , r , L [i] ) <= R [i] ) ) ; } } return ans ; }

컴파일 시 표준 에러 (stderr) 메시지

werewolf.cpp: In function 'int query(int, int, int, int, int, int)':
werewolf.cpp:41:25: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |                 if ( it == tree [node] .size () ) return 1e9 ;
      |                      ~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...