oj.uz

Submission #575204

# Submission time Handle Problem Language Result Execution time Memory
575204 2022-06-09T22:50:54 Z chonka Jail (JOI22_jail) C++17
0 / 100
 5000 ms 31472 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31360 KB Output is correct
2 Correct 16 ms 31360 KB Output is correct
3 Correct 17 ms 31316 KB Output is correct
4 Execution timed out 5021 ms 31380 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31316 KB Output is correct
2 Correct 15 ms 31380 KB Output is correct
3 Execution timed out 5063 ms 31472 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31316 KB Output is correct
2 Correct 15 ms 31380 KB Output is correct
3 Execution timed out 5063 ms 31472 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31316 KB Output is correct
2 Correct 15 ms 31380 KB Output is correct
3 Execution timed out 5063 ms 31472 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31316 KB Output is correct
2 Correct 15 ms 31380 KB Output is correct
3 Execution timed out 5063 ms 31472 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31328 KB Output is correct
2 Correct 17 ms 31356 KB Output is correct
3 Correct 17 ms 31388 KB Output is correct
4 Correct 16 ms 31272 KB Output is correct
5 Execution timed out 5080 ms 31404 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31360 KB Output is correct
2 Correct 16 ms 31360 KB Output is correct
3 Correct 17 ms 31316 KB Output is correct
4 Execution timed out 5021 ms 31380 KB Time limit exceeded
5 Halted 0 ms 0 KB -