oj.uz

Submission #647106

# Submission time Handle Problem Language Result Execution time Memory
647106 2022-10-01T15:22:59 Z chonka Werewolf (IOI18_werewolf) C++17
100 / 100
 1093 ms 118976 KB 
#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 ] ) {
            if ( i < x ) { 
                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 ] ) {
            if ( i > x ) { 
                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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19156 KB Output is correct
2 Correct 13 ms 19104 KB Output is correct
3 Correct 11 ms 19148 KB Output is correct
4 Correct 13 ms 19156 KB Output is correct
5 Correct 12 ms 19096 KB Output is correct
6 Correct 11 ms 19156 KB Output is correct
7 Correct 11 ms 19156 KB Output is correct
8 Correct 11 ms 19116 KB Output is correct
9 Correct 11 ms 19156 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19156 KB Output is correct
2 Correct 13 ms 19104 KB Output is correct
3 Correct 11 ms 19148 KB Output is correct
4 Correct 13 ms 19156 KB Output is correct
5 Correct 12 ms 19096 KB Output is correct
6 Correct 11 ms 19156 KB Output is correct
7 Correct 11 ms 19156 KB Output is correct
8 Correct 11 ms 19116 KB Output is correct
9 Correct 11 ms 19156 KB Output is correct
10 Correct 17 ms 20308 KB Output is correct
11 Correct 16 ms 20340 KB Output is correct
12 Correct 16 ms 20180 KB Output is correct
13 Correct 17 ms 20640 KB Output is correct
14 Correct 20 ms 20636 KB Output is correct
15 Correct 17 ms 20448 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 732 ms 87040 KB Output is correct
2 Correct 866 ms 101912 KB Output is correct
3 Correct 705 ms 96240 KB Output is correct
4 Correct 661 ms 94168 KB Output is correct
5 Correct 711 ms 94424 KB Output is correct
6 Correct 759 ms 95080 KB Output is correct
7 Correct 622 ms 94172 KB Output is correct
8 Correct 751 ms 101920 KB Output is correct
9 Correct 582 ms 95800 KB Output is correct
10 Correct 471 ms 93688 KB Output is correct
11 Correct 531 ms 93600 KB Output is correct
12 Correct 544 ms 93196 KB Output is correct
13 Correct 835 ms 110028 KB Output is correct
14 Correct 757 ms 109928 KB Output is correct
15 Correct 742 ms 110036 KB Output is correct
16 Correct 743 ms 110024 KB Output is correct
17 Correct 672 ms 94180 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19156 KB Output is correct
2 Correct 13 ms 19104 KB Output is correct
3 Correct 11 ms 19148 KB Output is correct
4 Correct 13 ms 19156 KB Output is correct
5 Correct 12 ms 19096 KB Output is correct
6 Correct 11 ms 19156 KB Output is correct
7 Correct 11 ms 19156 KB Output is correct
8 Correct 11 ms 19116 KB Output is correct
9 Correct 11 ms 19156 KB Output is correct
10 Correct 17 ms 20308 KB Output is correct
11 Correct 16 ms 20340 KB Output is correct
12 Correct 16 ms 20180 KB Output is correct
13 Correct 17 ms 20640 KB Output is correct
14 Correct 20 ms 20636 KB Output is correct
15 Correct 17 ms 20448 KB Output is correct
16 Correct 732 ms 87040 KB Output is correct
17 Correct 866 ms 101912 KB Output is correct
18 Correct 705 ms 96240 KB Output is correct
19 Correct 661 ms 94168 KB Output is correct
20 Correct 711 ms 94424 KB Output is correct
21 Correct 759 ms 95080 KB Output is correct
22 Correct 622 ms 94172 KB Output is correct
23 Correct 751 ms 101920 KB Output is correct
24 Correct 582 ms 95800 KB Output is correct
25 Correct 471 ms 93688 KB Output is correct
26 Correct 531 ms 93600 KB Output is correct
27 Correct 544 ms 93196 KB Output is correct
28 Correct 835 ms 110028 KB Output is correct
29 Correct 757 ms 109928 KB Output is correct
30 Correct 742 ms 110036 KB Output is correct
31 Correct 743 ms 110024 KB Output is correct
32 Correct 672 ms 94180 KB Output is correct
33 Correct 793 ms 97064 KB Output is correct
34 Correct 344 ms 53000 KB Output is correct
35 Correct 863 ms 102368 KB Output is correct
36 Correct 760 ms 96880 KB Output is correct
37 Correct 882 ms 100976 KB Output is correct
38 Correct 854 ms 98176 KB Output is correct
39 Correct 772 ms 118976 KB Output is correct
40 Correct 877 ms 107628 KB Output is correct
41 Correct 691 ms 98396 KB Output is correct
42 Correct 586 ms 94644 KB Output is correct
43 Correct 1093 ms 109076 KB Output is correct
44 Correct 916 ms 99732 KB Output is correct
45 Correct 795 ms 116944 KB Output is correct
46 Correct 814 ms 116924 KB Output is correct
47 Correct 982 ms 110168 KB Output is correct
48 Correct 850 ms 109980 KB Output is correct
49 Correct 837 ms 110100 KB Output is correct
50 Correct 749 ms 109932 KB Output is correct
51 Correct 877 ms 106852 KB Output is correct
52 Correct 878 ms 106828 KB Output is correct