Submission #575204

#	Time	Username	Problem	Language	Result	Execution time	Memory
575204		chonka	Jail (JOI22_jail)	C++17	0 / 100	5080 ms	31472 KiB

jail

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int MAXN = 120007 , LOG = 20 ;

int n , m ;
vector < int > v[ MAXN ] ;
pair < int , int > a[ MAXN ] ;

int sz[ MAXN ] , heavy[ MAXN ] , LCA[ MAXN ][ LOG ] , lvl[ MAXN ] ;
int root[ MAXN ] , pos_in_tree[ MAXN ] ;
int id_fst[ MAXN ] , id_lst[ MAXN ] ;

void dfs ( int vertex , int lst ) {
    sz[ vertex ] = 1 ;
    for ( int i = 1 ; i < LOG ; ++ i ) {
        LCA[ vertex ][ i ] = LCA[ LCA[ vertex ][ i - 1 ] ][ i - 1 ] ;
    }
    int mx = -1 , id = 0 ;
    for ( auto x : v[ vertex ] ) {
        if ( x == lst ) { continue ; }
        LCA[ x ][ 0 ] = vertex ;
        lvl[ x ] = lvl[ vertex ] + 1 ;
        dfs ( x , vertex ) ;
        sz[ vertex ] += sz[ x ] ;
        if ( mx < sz[ x ] ) {
            mx = sz[ x ] ;
            id = x ;
        }
    }
    heavy[ vertex ] = id ;
}

int get_LCA ( int x , int y ) {
    for ( int i = LOG - 1 ; i >= 0 ; -- i ) {
        if ( lvl[ x ] - ( 1 << i ) >= lvl[ y ] ) {
            x = LCA[ x ][ i ] ;
        }
        if ( lvl[ y ] - ( 1 << i ) >= lvl[ x ] ) {
            y = LCA[ y ][ i ] ;
        }
    }
    for ( int i = LOG - 1 ; i >= 0 ; -- i ) {
        if ( LCA[ x ][ i ] != LCA[ y ][ i ] ) {
            x = LCA[ x ][ i ] ;
            y = LCA[ y ][ i ] ;
        }
    }
    if ( x != y ) { x = LCA[ x ][ 0 ] ; }
    return x ;
}

int move_up ( int x , int cnt ) {
    for ( int i = LOG - 1 ; i >= 0 ; -- i ) {
        if ( cnt >= ( 1 << i ) ) {
            x = LCA[ x ][ i ] ;
        }
    }
    return x ;
}

vector < int > adj[ 6 * MAXN ] ;

class Tree {
public :
    int in_vert[ 4 * MAXN ] , out_vert[ 4 * MAXN ] ;
    int tp = 0 ;
    vector < int > tr[ 4 * MAXN ] ;
    void init ( int where , int IL , int IR ) {
        in_vert[ where ] = ++ tp ;
        out_vert[ where ] = ++ tp ;
        tr[ where ].clear ( ) ;
        if ( IL == IR ) { return ; }
        int mid = ( IL + IR ) / 2 ;
        init ( 2 * where , IL , mid ) ;
        init ( 2 * where + 1 , mid + 1 , IR ) ;
    }
    void add ( int where , int IL , int IR , int CURL , int CURR , int nw ) {
        if ( IL > IR || CURL > CURR ) { return ; }
        if ( IR < CURL || CURR < IL ) { return ; }
        if ( CURL <= IL && IR <= CURR ) {
            tr[ where ].push_back ( nw ) ;
            adj[ in_vert[ where ] ].push_back ( nw ) ;
            adj[ nw ].push_back ( out_vert[ where ] ) ;
            return ;
        }
        int mid = ( IL + IR ) / 2 ;
        add ( 2 * where , IL , mid , CURL , CURR , nw ) ;
        add ( 2 * where + 1 , mid + 1 , IR , CURL , CURR , nw ) ;
    }
    void connect ( int where , int IL , int IR , int pos , int val , bool fl ) {
        if ( fl == true ) {
            adj[ out_vert[ where ] ].push_back ( val ) ;
        }
        else {
            adj[ val ].push_back ( in_vert[ where ] ) ;
        }
        if ( IL == IR ) { return ; }
        int mid = ( IL + IR ) / 2 ;
        if ( pos <= mid ) {
            connect ( 2 * where , IL , mid , pos , val , fl ) ;
        }
        else {
            connect ( 2 * where + 1 , mid + 1 , IR , pos , val , fl ) ;
        }
    }
};
Tree w ;
int used[ 6 * MAXN ] ;

void input ( ) {
    cin >> n ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        v[ i ].clear ( ) ;
        id_fst[ i ] = id_lst[ i ] = 0 ;
    }
    for ( int x , y , i = 1 ; i < n ; ++ i ) {
        cin >> x >> y ;
        v[ x ].push_back ( y ) ;
        v[ y ].push_back ( x ) ;
    }
    cin >> m ;
    for ( int i = 1 ; i <= m ; ++ i ) {
        cin >> a[ i ].first >> a[ i ].second ;
        id_fst[ a[ i ].first ] = i ;
        id_lst[ a[ i ].second ] = i ;
    }
    for ( int i = 1 ; i <= m + 5 * n ; ++ i ) {
        used[ i ] = 0 ;
        adj[ i ].clear ( ) ;
    }
}


bool dfs ( int vertex ) {
    used[ vertex ] = 1 ;
    for ( auto x : adj[ vertex ] ) {
        if ( used[ x ] == 1 ) { return true ; }
        if ( used[ x ] == 0 ) {
            dfs ( x ) ;
        }
    }
    used[ vertex ] = 2 ;
    return false ;
}

void solve ( ) {
    dfs ( 1 , -1 ) ;
    int tp = 0 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( heavy[ LCA[ i ][ 0 ] ] != i ) {
            int x = i ;
            while ( x > 0 ) {
                root[ x ] = i ;
                pos_in_tree[ x ] = ++ tp ;
                x = heavy[ x ] ;
            }
        }
    }
    w.tp = m ;
    w.init ( 1 , 1 , n ) ;
    for ( int i = 1 ; i <= m ; ++ i ) {
        int x = a[ i ].first , y = a[ i ].second ;
        int aux = get_LCA ( x , y ) ;
        if ( aux != x && aux != y ) {
            x = LCA[ x ][ 0 ] , y = LCA[ y ][ 0 ] ;
        }
        else {
            if ( lvl[ x ] > lvl[ y ] ) { swap ( x , y ) ; }
            x = move_up ( y , lvl[ y ] - lvl[ x ] - 1 ) ;
            y = LCA[ y ][ 0 ] ;
            if ( lvl[ x ] > lvl[ y ] ) { continue ; }
        }
        while ( root[ x ] != root[ y ] ) {
            if ( lvl[ root[ x ] ] < lvl[ root[ y ] ] ) { swap ( x , y ) ; }
            w.add ( 1 , 1 , n , pos_in_tree[ root[ x ] ] , pos_in_tree[ x ] , i ) ;
            x = LCA[ root[ x ] ][ 0 ] ;
        }
        if ( pos_in_tree[ x ] > pos_in_tree[ y ] ) { swap ( x , y ) ; }
        w.add ( 1 , 1 , n , pos_in_tree[ x ] , pos_in_tree[ y ] , i ) ;
    }
    for ( int i = 1 ; i <= m ; ++ i ) {
        w.connect ( 1 , 1 , n , pos_in_tree[ a[ i ].first ] , i , true ) ;
        w.connect ( 1 , 1 , n , pos_in_tree[ a[ i ].second ] , i , false ) ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( id_fst[ i ] > 0 && id_lst[ i ] > 0 ) {
            adj[ id_lst[ i ] ].push_back ( id_fst[ i ] ) ;
        }
    }
    for ( int i = 1 ; i <= m + 5 * n ; ++ i ) {
        if ( used[ i ] == 0 ) {
            if ( dfs ( i ) == true ) {
                cout << "No\n" ;
                return ;
            }
        }
    }
    cout << "Yes\n" ;
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t ;
    /// t = 1 ;
    /// scanf ( "%d" , &t ) ;
    cin >> t ;
    while ( t -- ) {
        input ( ) ;
        solve ( ) ;
    }
    return 0 ;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23