Submission #798079

#	Time	Username	Problem	Language	Result	Execution time	Memory
798079		lollipop	Werewolf (IOI18_werewolf)	C++17	100 / 100	1200 ms	203848 KiB

werewolf

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod =  1000000007 ;
const int mod1 = 998244353 ;
const int N = 4e5 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;

#include "werewolf.h"
int n , pp[ N ] , ss[ N ] ; 
vector < int > V[ N ] , v[ 2 ][ N ] ;

// DSU 
void create( int node ){
	 pp[ node ] = node ;
	 ss[ node ] = 1 ; return ;
}
int find( int node ){
	if( pp[ node ] == node ) return node ;
	return pp[ node ] = find( pp[ node ] ) ;
}
void unite( int a , int b ){
	 if( ss[ a ] < ss[ b ] ) swap( a , b ) ;
	 if( ss[ a ] == ss[ b ] ) ss[ a ] ++ ; 
	 pp[ b ] = a ; return ;
}
// Build the trees 
int cnt = n + 1 ; 
int app[ 2 ][ N ] ; 
void ad( int u , int tp ){
       create( cnt ) ;
	 app[ tp ][ u ] = u ;
	 app[ tp ][ cnt ] = u ;
	 set < int > se ;
	 se.insert( find( u ) ) ;
	 for( auto x : V[ u ] ){
	 	if( x > u && tp == 0 ) continue ;
	 	if( x < u && tp == 1 ) continue ; 
	 	se.insert( find( x ) ) ;
	 }
	 for( auto x : se ){
	 	v[ tp ][ cnt ].pb( x ) ;
	 	v[ tp ][ x ].pb( cnt ) ;
	 	unite( x , find( cnt ) ) ;
	 }
	 int x = find( cnt ) ; 
	 pp[ x ] = cnt ; pp[ cnt ] = cnt ;
	 ss[ cnt ] = ss[ x ] ; 
	 cnt ++ ;
	 return ;
}
// now go over those trees and calculate some useful stuff 
int p[ 2 ][ N ][ 20 ] , xx[ 20 ] , nmb[ 2 ][ N ] , timer = 1 , uno[ 2 ][ N ] ;
pair < int , int > lr[ 2 ][ N ] ;
pair < int , int > dfs( int node , int parent , int tp , int h ){
	 p[ tp ][ node ][ 0 ] = parent ;
	 for( int j = 1 ; j < 20 ; j ++ ){
	 	if( xx[ j ] > h ) p[ tp ][ node ][ j ] = -1 ;
	 	else p[ tp ][ node ][ j ] = p[ tp ][ p[ tp ][ node ][ j - 1 ] ][ j - 1 ] ;
	 }	 
	 pair < int , int > pp = { INT_MAX , -1 } ;
	 if( node <= n ){
	 	uno[ tp ][ timer ] = node ;
	 	nmb[ tp ][ node ] = timer ;
	 	pp = { timer , timer } ;
	 	timer ++ ;
	 }
	 for( auto x : v[ tp ][ node ] ){
	 	if( x == parent ) continue ;
	 	pair < int , int > pu ;
	 	pu = dfs( x , node , tp , h + 1 ) ;
	 	pp.f = min( pp.f , pu.f ) ;
	 	pp.s = max( pp.s , pu.s ) ;
	 }
	 lr[ tp ][ node ] = pp ;
	 return pp ;
}
// now how find useful parent of each of the important nodes in two trees 
int check( int tp , int cur , int nd ){
	 if( cur == -1 ) return -1 ;
	 if( tp == 0 && app[ tp ][ cur ] > nd ) return -1 ;
	 if( tp == 1 && app[ tp ][ cur ] < nd ) return -1 ;
	 return 1 ; 
}
int find_node( int node , int tp , int nd ){
	for( int j = 19 ; j >= 0 ; j -- ){
		if( check( tp , p[ tp ][ node ][ j ] , nd ) == 1 )
		  node = p[ tp ][ node ][ j ] ;
	}
	if( check( tp , p[ tp ][ node ][ 0 ] , nd ) == 1 ) return p[ tp ][ node ][ 0 ] ;
	return node ;
}
// now seg trees
int node[ 4 * N ] ;
void upd( int v , int vl , int vr , int pos ){
	 if( vl == vr ){
	 	node[ v ] = 1 ; return ;
	 }
	 int vm = ( vl + vr ) / 2 ;
	 if( vm >= pos ) upd( v + v , vl , vm , pos ) ;
	 else upd( v + v + 1 , vm + 1 , vr , pos ) ;
	 node[ v ] = node[ v + v ] + node[ v + v + 1 ] ;
	 return ;
}
int get( int v , int vl ,int vr , int l , int r ){
	if( l > r ) return 0 ;
	if( vl == l && vr == r ){
		return node[ v ] ;
	}
	int vm = ( vl + vr ) / 2 ;
	int a = get( v + v , vl , vm , l , min( r , vm ) ) ;
	int b = get( v + v + 1 , vm + 1 , vr , max( vm + 1 , l ) , r ) ;
	return ( a + b ) ; 
}
vector < int > del[ N ] , add[ N ] ;
int pas[ N ] ;
vector<int> check_validity(int N, vector<int> X, vector<int> Y,  vector<int> S, vector<int> E, vector<int> L, vector<int> R){
      xx[ 0 ] = 1 ;
      for( int j = 1 ; j < 20 ; j ++ ) xx[ j ] = xx[ j - 1 ] * 2 ;
	  FOR( i , X.size() ){
	        X[ i ] ++ ; Y[ i ] ++ ;
      	 V[ X[ i ] ].pb( Y[ i ] ) ;
      	 V[ Y[ i ] ].pb( X[ i ] ) ;
	  }
      n = N ; 
      // build first tree 
	  for( int j = 1 ; j <= 2 * n + 5 ; j ++ ) create( j ) ;
      cnt = n + 1 ; 
      for( int j = 1 ; j <= n ; j ++ ){
      	 ad( j , 0 ) ; 
	  }
      timer = 1 ;
      dfs( cnt - 1 , -1 , 0 , 0 ) ;
      // build second tree 
	  for( int j = 1 ; j <= 2 * n ; j ++ ) create( j ) ;
      cnt = n + 1 ; 
      for( int j = n ; j >= 1 ; j -- ){
      	 ad( j , 1 ) ; 
	  }
      timer = 1 ;
      dfs( cnt - 1 , -1 , 1 , 0 ) ; 
	  // now build calculate answer part
	  FOR( i , S.size() ){
	  	S[ i ] ++ ; R[ i ] ++ ; L[ i ] ++ ; E[ i ] ++ ; 
	  	 int node = find_node( S[ i ] , 1 , L[ i ] ) ;
	  	 int l , r ;
	  	 l = lr[ 1 ][ node ].f ;
	  	 r = lr[ 1 ][ node ].s ;
	  	 del[ l - 1 ].pb( i ) ;
	  	 add[ r ].pb( i ) ;
	  }
	  for( int j = 1 ; j <= n ; j ++ ){
	  	int node = uno[ 1 ][ j ] ;
	  	upd( 1 , 1 , n , nmb[ 0 ][ node ] ) ;
	  	for( auto x : del[ j ] ){
		  	int node = find_node( E[ x ] , 0 , R[ x ] ) ;
		  	int l , r ;
		  	l = lr[ 0 ][ node ].f ;
		  	r = lr[ 0 ][ node ].s ;	
			pas[ x ] -= get( 1 , 1 , n , l , r ) ;    	   	
		}
	  	for( auto x : add[ j ] ){
		  	int node = find_node( E[ x ] , 0 , R[ x ] ) ;
		  	int l , r ;
		  	l = lr[ 0 ][ node ].f ;
		  	r = lr[ 0 ][ node ].s ;	
		 // 	cout << E[ x ] << " " << R[ x ] << "  " << l << " " << r << " nd "<< node << endl ; 
		  	pas[ x ] += get( 1 , 1 , n , l , r ) ;
		}		
	  }     
      vector < int > ans ;
      FOR( i , S.size() ){
      	if( pas[ i ] > 0 ) ans.pb( 1 ) ; 
      	else ans.pb( 0 ) ; 
	  }
	  return ans ;
}



//
// namespace {
//
// int read_int() {
//   int x;
//   if (scanf("%d", &x) != 1) {
//     fprintf(stderr, "Error while reading input\n");
//     exit(1);
//   }
//   return x;
// }
//
// }  // namespace
//
// int main() {
//   int N = read_int();
//   int M = read_int();
//   int Q = read_int();
//   std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
//   for (int j = 0; j < M; ++j) {
//     X[j] = read_int();
//     Y[j] = read_int();
//   }
//   for (int i = 0; i < Q; ++i) {
//     S[i] = read_int();
//     E[i] = read_int();
//     L[i] = read_int();
//     R[i] = read_int();
//   }
//
//   std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
//   for (size_t i = 0; i < A.size(); ++i) {
//     printf("%d\n", A[i]);
//   }
//   return 0;
// }

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
  144 |    FOR( i , X.size() ){
      |         ~~~~~~~~~~~~                     
werewolf.cpp:144:4: note: in expansion of macro 'FOR'
  144 |    FOR( i , X.size() ){
      |    ^~~
werewolf.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
  167 |    FOR( i , S.size() ){
      |         ~~~~~~~~~~~~                     
werewolf.cpp:167:4: note: in expansion of macro 'FOR'
  167 |    FOR( i , S.size() ){
      |    ^~~
werewolf.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
  196 |       FOR( i , S.size() ){
      |            ~~~~~~~~~~~~                  
werewolf.cpp:196:7: note: in expansion of macro 'FOR'
  196 |       FOR( i , S.size() ){
      |       ^~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51