#include "werewolf.h"
using namespace std ;
const int MAXN = 2e5 + 7 ;
const int LOG = 18 ;
vector < int > v[ 2 ][ MAXN ] ;
int prv[ MAXN ] , rnk[ MAXN ] ;
int get ( int x ) {
if ( prv[ x ] == -1 ) { return x ; }
int y = get ( prv[ x ] ) ;
prv[ x ] = y ;
return y ;
}
void unite ( int x , int y , int type ) {
int k1 = get ( x ) , k2 = get ( y ) ;
if ( k1 != k2 ) {
if ( type == 0 ) {
if ( k1 > k2 ) { swap ( k1 , k2 ) ; }
}
else {
if ( k1 < k2 ) { swap ( k1 , k2 ) ; }
}
v[ type ][ k1 ].emplace_back ( k2 ) ;
prv[ k2 ] = k1 ;
}
}
vector < int > edges[ MAXN ] ;
int st[ 2 ][ MAXN ] , en[ 2 ][ MAXN ] ;
int ord[ 2 ][ MAXN ] ;
int LCA[ 2 ][ MAXN ][ LOG ] , lvl[ 2 ][ MAXN ] ;
int tp[ 2 ] ;
void dfs ( int x , int id ) {
st[ id ][ x ] = ++ tp[ id ] ;
ord[ id ][ tp[ id ] ] = x ;
for ( int i = 1 ; i < LOG ; ++ i ) {
LCA[ id ][ x ][ i ] = LCA[ id ][ LCA[ id ][ x ][ i - 1 ] ][ i - 1 ] ;
}
for ( auto y : v[ id ][ x ] ) {
lvl[ id ][ y ] = lvl[ id ][ x ] + 1 ;
LCA[ id ][ y ][ 0 ] = x ;
dfs ( y , id ) ;
}
en[ id ][ x ] = tp[ id ] ;
}
class Tree {
public :
int tr[ 4 * MAXN ] ;
void init ( int w , int l , int r ) {
tr[ w ] = 0 ;
if ( l == r ) { return ; }
int mid = ( l + r ) / 2 ;
init ( 2 * w , l , mid ) ;
init ( 2 * w + 1 , mid + 1 , r ) ;
}
void update ( int w , int l , int r , int pos , int add ) {
tr[ w ] += add ;
if ( l == r ) { return ; }
int mid = ( l + r ) / 2 ;
if ( pos <= mid ) { update ( 2 * w , l , mid , pos , add ) ; }
else { update ( 2 * w + 1 , mid + 1 , r , pos , add ) ; }
}
int query ( int w , int l , int r , int st , int en ) {
if ( l > r || st > en ) { return 0 ; }
if ( r < st || en < l ) { return 0 ; }
if ( st <= l && r <= en ) { return tr[ w ] ; }
int mid = ( l + r ) / 2 ;
return query ( 2 * w , l , mid , st , en ) + query ( 2 * w + 1 , mid + 1 , r , st , en ) ;
}
};
Tree w ;
int rem[ MAXN ] ;
vector < int > evt[ MAXN ] ;
std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
for ( int i = 1 ; i <= n ; ++ i ) {
prv[ i ] = -1 , rnk[ i ] = 0 ;
}
int m = X.size ( ) ;
for ( int i = 0 ; i < m ; ++ i ) {
++ X[ i ] , ++ Y[ i ] ;
edges[ X[ i ] ].push_back ( Y[ i ] ) ;
edges[ Y[ i ] ].push_back ( X[ i ] ) ;
}
for ( int i = n ; i >= 1 ; -- i ) {
for ( auto x : edges[ i ] ) {
unite ( i , x , 0 ) ;
}
}
for ( int i = 1 ; i <= n ; ++ i ) {
prv[ i ] = -1 , rnk[ i ] = 0 ;
}
for ( int i = 1 ; i <= n ; ++ i ) {
for ( auto x : edges[ i ] ) {
unite ( i , x , 1 ) ;
}
}
dfs ( 1 , 0 ) ;
dfs ( n , 1 ) ;
int Q = S.size ( ) ;
vector < int > ret ( Q ) ;
for ( int i = 0 ; i < Q ; ++ i ) {
rem[ i ] = -1 ;
++ S[ i ] , ++ E[ i ] ;
++ L[ i ] , ++ R[ i ] ;
for ( int j = LOG - 1 ; j >= 0 ; -- j ) {
if ( LCA[ 0 ][ S[ i ] ][ j ] > 0 && LCA[ 0 ][ S[ i ] ][ j ] >= L[ i ] ) {
S[ i ] = LCA[ 0 ][ S[ i ] ][ j ] ;
}
if ( LCA[ 1 ][ E[ i ] ][ j ] > 0 && LCA[ 1 ][ E[ i ] ][ j ] <= R[ i ] ) {
E[ i ] = LCA[ 1 ][ E[ i ] ][ j ] ;
}
}
evt[ st[ 0 ][ S[ i ] ] - 1 ].push_back ( i ) ;
evt[ en[ 0 ][ S[ i ] ] ].push_back ( i ) ;
}
w.init ( 1 , 1 , n ) ;
for ( int i = 0 ; i <= n ; ++ i ) {
if ( i > 0 ) {
w.update ( 1 , 1 , n , st[ 1 ][ ord[ 0 ][ i ] ] , 1 ) ;
}
for ( auto id : evt[ i ] ) {
if ( rem[ id ] == -1 ) {
rem[ id ] = w.query ( 1 , 1 , n , st[ 1 ][ E[ id ] ] , en[ 1 ][ E[ id ] ] ) ;
}
else {
int sr = w.query ( 1 , 1 , n , st[ 1 ][ E[ id ] ] , en[ 1 ][ E[ id ] ] ) ;
if ( sr > rem[ id ] ) { ret[ id ] = 1 ; }
else { ret[ id ] = 0 ; }
}
}
}
return ret ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
733 ms |
93280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
