oj.uz

Submission #798079

# Submission time Handle Problem Language Result Execution time Memory
798079 2023-07-30T10:57:13 Z lollipop Werewolf (IOI18_werewolf) C++17
100 / 100
 1200 ms 203848 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47444 KB Output is correct
2 Correct 23 ms 47352 KB Output is correct
3 Correct 23 ms 47288 KB Output is correct
4 Correct 23 ms 47280 KB Output is correct
5 Correct 22 ms 47444 KB Output is correct
6 Correct 22 ms 47308 KB Output is correct
7 Correct 24 ms 47368 KB Output is correct
8 Correct 23 ms 47444 KB Output is correct
9 Correct 23 ms 47380 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47444 KB Output is correct
2 Correct 23 ms 47352 KB Output is correct
3 Correct 23 ms 47288 KB Output is correct
4 Correct 23 ms 47280 KB Output is correct
5 Correct 22 ms 47444 KB Output is correct
6 Correct 22 ms 47308 KB Output is correct
7 Correct 24 ms 47368 KB Output is correct
8 Correct 23 ms 47444 KB Output is correct
9 Correct 23 ms 47380 KB Output is correct
10 Correct 29 ms 49492 KB Output is correct
11 Correct 30 ms 49484 KB Output is correct
12 Correct 31 ms 49416 KB Output is correct
13 Correct 30 ms 49696 KB Output is correct
14 Correct 30 ms 49716 KB Output is correct
15 Correct 31 ms 49468 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1044 ms 183552 KB Output is correct
2 Correct 1016 ms 188320 KB Output is correct
3 Correct 863 ms 183448 KB Output is correct
4 Correct 804 ms 181880 KB Output is correct
5 Correct 853 ms 182104 KB Output is correct
6 Correct 935 ms 183060 KB Output is correct
7 Correct 882 ms 181988 KB Output is correct
8 Correct 840 ms 188300 KB Output is correct
9 Correct 655 ms 182848 KB Output is correct
10 Correct 560 ms 181056 KB Output is correct
11 Correct 647 ms 181312 KB Output is correct
12 Correct 725 ms 180736 KB Output is correct
13 Correct 997 ms 191772 KB Output is correct
14 Correct 1037 ms 191884 KB Output is correct
15 Correct 967 ms 191860 KB Output is correct
16 Correct 995 ms 192000 KB Output is correct
17 Correct 860 ms 182208 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47444 KB Output is correct
2 Correct 23 ms 47352 KB Output is correct
3 Correct 23 ms 47288 KB Output is correct
4 Correct 23 ms 47280 KB Output is correct
5 Correct 22 ms 47444 KB Output is correct
6 Correct 22 ms 47308 KB Output is correct
7 Correct 24 ms 47368 KB Output is correct
8 Correct 23 ms 47444 KB Output is correct
9 Correct 23 ms 47380 KB Output is correct
10 Correct 29 ms 49492 KB Output is correct
11 Correct 30 ms 49484 KB Output is correct
12 Correct 31 ms 49416 KB Output is correct
13 Correct 30 ms 49696 KB Output is correct
14 Correct 30 ms 49716 KB Output is correct
15 Correct 31 ms 49468 KB Output is correct
16 Correct 1044 ms 183552 KB Output is correct
17 Correct 1016 ms 188320 KB Output is correct
18 Correct 863 ms 183448 KB Output is correct
19 Correct 804 ms 181880 KB Output is correct
20 Correct 853 ms 182104 KB Output is correct
21 Correct 935 ms 183060 KB Output is correct
22 Correct 882 ms 181988 KB Output is correct
23 Correct 840 ms 188300 KB Output is correct
24 Correct 655 ms 182848 KB Output is correct
25 Correct 560 ms 181056 KB Output is correct
26 Correct 647 ms 181312 KB Output is correct
27 Correct 725 ms 180736 KB Output is correct
28 Correct 997 ms 191772 KB Output is correct
29 Correct 1037 ms 191884 KB Output is correct
30 Correct 967 ms 191860 KB Output is correct
31 Correct 995 ms 192000 KB Output is correct
32 Correct 860 ms 182208 KB Output is correct
33 Correct 1116 ms 186184 KB Output is correct
34 Correct 328 ms 82620 KB Output is correct
35 Correct 1143 ms 190328 KB Output is correct
36 Correct 1056 ms 185020 KB Output is correct
37 Correct 1200 ms 189132 KB Output is correct
38 Correct 1048 ms 185804 KB Output is correct
39 Correct 1075 ms 203848 KB Output is correct
40 Correct 1022 ms 193224 KB Output is correct
41 Correct 844 ms 186056 KB Output is correct
42 Correct 751 ms 182124 KB Output is correct
43 Correct 1180 ms 194444 KB Output is correct
44 Correct 1066 ms 187088 KB Output is correct
45 Correct 993 ms 201000 KB Output is correct
46 Correct 991 ms 200580 KB Output is correct
47 Correct 1103 ms 191932 KB Output is correct
48 Correct 1125 ms 191856 KB Output is correct
49 Correct 1098 ms 192012 KB Output is correct
50 Correct 990 ms 191828 KB Output is correct
51 Correct 923 ms 193032 KB Output is correct
52 Correct 930 ms 192912 KB Output is correct