Submission #647103

#	Time	Username	Problem	Language	Result	Execution time	Memory
647103		chonka	Werewolf (IOI18_werewolf)	C++17	0 / 100	733 ms	93280 KiB

werewolf

#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 ;
}

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