Submission #287331

#	Time	Username	Problem	Language	Result	Execution time	Memory
287331		infinite_iq	Werewolf (IOI18_werewolf)	C++14	34 / 100	1182 ms	51576 KiB

werewolf

    #include <bits/stdc++.h>
    using namespace std ;
    #define mid (l+r)/2
    #define le node*2
    #define ri node*2+1
    #define pb push_back
    #define C continue 
    #define lb lower_bound
    #define ub upper_bound
    #define ins insert 
    #define era erase 
    #define all(x) x.begin(), x.end()
    typedef vector < int > vi ;
    #include "werewolf.h"
    int n , m , q ;
    vi v [200009] , ans ;
    int a [200009] , pos [200009] ;
    int stop [200009][2][2] ;
    void dfs ( int node , int p , int ord ) {
            a [ord] = node ;
            for ( auto u : v [node] ) {
                    if ( u == p ) C ;
                    dfs ( u , node , ord + 1 ) ;
            }
    }
    vi check_validity ( int N , vi X , vi Y, vi S, vi E , vi L , vi R ) {
            n = N , m = X .size () , q = S .size () ;
            for ( int i = 0 ; i < m ; i ++ ) {
                    int a = X [i] , b = Y [i] ;
                    v [a] .pb ( b ) ;
                    v [b] .pb ( a ) ;
            }
            for ( int i = 0 ; i < n ; i ++ ) {
                    if ( v [i] .size () == 1 ) {
                            dfs ( i , i , 0 ) ;
                            break ;
                    }
            }
            set < int > s ;
            for ( int i = 0 ; i < n ; i ++ ) {
                    pos [ a [i] ] = i ;
                    v [i] .clear () ;
                    s .ins ( i ) ;
            }
            for ( int i = 0 ; i < q ; i ++ ) {
                    v [ R [i] ] .pb ( i ) ;
                    swap ( S [i] , E [i] ) ;
            }
            for ( int i = 0 ; i < n ; i ++ ) {
                    s .era ( pos [i] ) ;
                    for ( auto u : v [i] ) {
                            int l = pos[S [u]] , r = pos [E [u]] , id = u ;
                            if ( l > r ) swap ( l , r ) ;
                            auto it = s .lb ( l ) ;
                            stop [id][0][0] = ( it == s.end () ? r : min ( (int)(*it -1) , r ) ) ;
                            it = s .ub ( r ) ;
                            stop [id][0][1] = ( it == s.begin () ? l : max ( (int)(*(--it) + 1) , l ) ) ;
                    }
            }
            for ( int i = 0 ; i < n ; i ++ ) {
                    v [i] .clear () ;
                    s .ins ( i ) ;
            }
            for ( int i = 0 ; i < q ; i ++ ) {
                    v [ L [i] ] .pb ( i ) ;
            }
            for ( int i = n - 1 ; i >= 0 ; i -- ) {
                    s .era ( pos [i] ) ;
                    for ( auto u : v [i] ) {
                            int l = pos [S [u]] , r = pos [E [u]] , id = u ;
                            if ( l > r ) swap ( l , r ) ;
                            auto it = s .lb ( l ) ;
                            stop [id][1][0] = ( it == s.end () ? r : min ( (int)(*it -1) , r ) ) ;
                            it = s .ub ( r ) ;
                            stop [id][1][1] = ( it == s.begin () ? l : max ( (int)(*(--it) + 1) , l ) ) ;
                    }
            }
            for ( int i = 0 ; i < q ; i ++ ) {
                    int st = pos [S [i]] , en = pos [E [i]] ;
                    if ( st <= en ) {
                            int bound1 = stop [i][0][0] ;
                            int bound2 = stop [i][1][1] ;
                            if ( bound1 < st || bound2 > en || bound1 < bound2 ) {
                                    ans .pb ( 0 ) ;
                                    C ;
                            }
                            int l = bound2 , r = bound1 ;
                            ans .pb ( 1 ) ;
                    }
                    else {
                            int bound1 = stop [i][0][1] ;
                            int bound2 = stop [i][1][0] ;
                            if ( bound1 > st || bound2 < en || bound2 < bound1 ) {
                                    ans .pb ( 0 ) ;
                                    C ;
                            }
                            int l = bound1 , r = bound2 ;
                            ans .pb ( 1 ) ;
                    }
            }
            return ans ;
    }

Compilation message (stderr)

werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:87:33: warning: unused variable 'l' [-Wunused-variable]
   87 |                             int l = bound2 , r = bound1 ;
      |                                 ^
werewolf.cpp:87:46: warning: unused variable 'r' [-Wunused-variable]
   87 |                             int l = bound2 , r = bound1 ;
      |                                              ^
werewolf.cpp:97:33: warning: unused variable 'l' [-Wunused-variable]
   97 |                             int l = bound1 , r = bound2 ;
      |                                 ^
werewolf.cpp:97:46: warning: unused variable 'r' [-Wunused-variable]
   97 |                             int l = bound1 , r = bound2 ;
      |                                              ^

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