Submission #631492

#	Time	Username	Problem	Language	Result	Execution time	Memory
631492		mdn2002	Jail (JOI22_jail)	C++14	0 / 100	14 ms	19108 KiB

jail

#include<bits/stdc++.h>
using namespace std;
int n , m , st [200005][21] , dp [200005] , s [200005] , t [200005] , vis [200005] , ff;
vector < int > gr [200005] , grr [200005] , ss [200005] , tt [200005];
int tree [800005];
void up ( int nod , int l , int r , int x , int val )
{
    if ( x < l || r < x ) return;
    if ( l == r )
    {
        tree [nod] = val;
        return;
    }
    int mid = ( l + r ) / 2;
    up ( nod * 2 , l , mid , x , val );
    up ( nod * 2 + 1 , mid + 1 , r , x , val );
    tree [nod] = tree [ nod * 2 ] + tree [ nod * 2 + 1 ];
}
long long qr ( int nod , int l , int r , int x , int y )
{
    if ( y < l || r < x ) return 0;
    if ( x <= l && r <= y ) return tree [nod];
    int mid = ( l + r ) / 2;
    return ( qr ( nod * 2 , l , mid , x , y ) + qr ( nod * 2 + 1 , mid + 1 , r , x , y ) );
}
void dfs ( int x , int p )
{
    dp [x] = dp [p] + 1;
    st [x][0] = p;
    for ( auto u : gr [x] )
    {
        if ( u == p ) continue;
        dfs ( u , x );
    }
}
void dfss ( int x )
{
    vis [x] = 1;
    for ( auto u : grr [x] )
    {
        if ( vis [u] == 1 )
        {
            ff = 1;
            continue;
        }
        else if ( vis [u] == 2 ) continue;
        else dfss ( u );
    }
    vis [x] = 2;
}
int lca ( int x , int y )
{
    if ( dp [x] > dp [y] ) swap ( x , y );
    int dif = dp [y] - dp [x];
    for ( int i = 0 ; i <= 20 ; i ++ )
    {
        if ( ( dif & ( 1 << i ) ) ) y = st [y][i];
    }
    if ( x == y ) return x;
    for ( int i = 20 ; i >= 0 ; i -- )
    {
        if ( st [x][i] != st [y][i] )
        {
            x = st [x][i];
            y = st [y][i];
        }
    }
    return st [x][0];
}
int inbet ( int x , int y , int z )
{
    if ( dp [z] > dp [x] && dp [z] > dp [y] ) return 0;
    int aa = lca ( x , y );
    if ( dp [aa] > dp [z] ) return 0;
    int a = lca ( x , z );
    int b = lca ( y , z );
    if ( a == z || b == z ) return 1;
    return 0;
}
int main()
{
    int q;
    cin >> q;
    while ( q -- )
    {
        ff = 0;
        cin >> n;
        int ffff = 0;
        for ( int i = 1 ; i <= n ; i ++ )
        {
            gr [i] . clear ();
            grr [i] . clear ();
            ss [i] . clear ();
            tt [i] . clear ();
            dp [i] = 0;
            vis [i] = 0;
            for ( int j = 0 ; j <= 20 ; j ++ ) st [i][j] = 0;
        }
        for ( int i = 0 ; i < n - 1 ; i ++ )
        {
            int x , y;
            cin >> x >> y;
            if ( x != i + 1 || y != i + 2 ) ffff = 1;
            gr [x] . push_back ( y );
            gr [y] . push_back ( x );
        }
        dfs ( 1 , 0 );
        for ( int i = 1 ; i <= 20 ; i ++ )
        {
            for ( int j = 1 ; j <= n ; j ++ ) st [j][i] = st [ st [j][ i - 1 ] ][ i - 1 ];
        }
        cin >> m;
        for ( int i = 1 ; i <= m ; i ++ )
        {
            cin >> s [i] >> t [i];
            ss [ s [i] ] . push_back ( i );
            tt [ t [i] ] . push_back ( i );
        }
        if ( ffff == 0 )
        {
            int ks = 1;
            vector < pair < int , int > > vv;
            for ( int i = 1 ; i <= m ; i ++ )
            {
                if ( s [i] < t [i] ) vv . push_back ( { s [i] , t [i] } );
                up ( 1 , 0 , n , s [i] , 1 );
            }
            sort ( vv . begin () , vv . end () );
            for ( int i = vv . size () - 1 ; i >= 0 ; i -- )
            {
                int x = vv [i] . first , y = vv [i] . second;
                if ( qr ( 1 , 0 , n , x + 1 , y ) == 1 ) ks = 1;
                up ( 1 , 0 , n , x , 0 );
                up ( 1 , 0 , n , y , 1 );
            }
            vv . clear ();
            for ( int i = 1 ; i <= m ; i ++ )
            {
                if ( s [i] > t [i] ) vv . push_back ( { t [i] , s [i] } );
            }
            sort ( vv . begin () , vv . end () );
            for ( int i = vv . size () - 1 ; i >= 0 ; i -- )
            {
                int x = vv [i] . first , y = vv [i] . second;
                if ( qr ( 1 , 0 , n , x , y - 1 ) == 1 ) ks = 1;
                up ( 1 , 0 , n , x , 1 );
                up ( 1 , 0 , n , y , 0 );
            }
            if ( ks ) cout << "No" << endl;
            else cout << "Yes" << endl;
        }
        else
        {
            if ( m <= 500 )
            {
                for ( int i = 1 ; i <= m ; i ++ )
                {
                    for ( int j = 1 ; j <= m ; j ++ )
                    {
                        if ( i == j ) continue;
                        if ( inbet ( s [i] , t [i] , s [j] ) ) grr [i] . push_back ( j );
                        if ( inbet ( s [i] , t [i] , t [j] ) ) grr [j] . push_back ( i );
                    }
                }
            }
            else
            {
                for ( int i = 1 ; i <= m ; i ++ )
                {
                    int a = lca ( s [i] , t [i] ) , x = s [i];
                    while ( true )
                    {
                        for ( auto u : ss [x] )
                        {
                            if ( u != i ) grr [i] . push_back ( u );
                        }
                        for ( auto u : tt [x] )
                        {
                            if ( u != i ) grr [u] . push_back ( i );
                        }
                        if ( x == a ) break;
                        x = st [x][0];
                    }
                    x = t [i];
                    while ( true )
                    {
                        for ( auto u : ss [x] )
                        {
                            if ( u != i ) grr [i] . push_back ( u );
                        }
                        for ( auto u : tt [x] )
                        {
                            if ( u != i ) grr [u] . push_back ( i );
                        }
                        if ( a == x ) break;
                        x = st [x][0];
                    }
                }
            }
            for ( int i = 1 ; i <= m ; i ++ )
            {
                if ( vis [i] == 0 ) dfss ( i );
            }
            if ( ff ) cout << "No" << endl;
            else cout << "Yes" << endl;
        }
    }
}

/*
1
4
1 2
2 3
3 4
2
1 3
4 2
*/

• 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