oj.uz

Submission #631771

# Submission time Handle Problem Language Result Execution time Memory
631771 2022-08-18T17:25:54 Z mdn2002 Jail (JOI22_jail) C++14
21 / 100
 607 ms 62184 KB 
#include<bits/stdc++.h>
using namespace std;
int n , m , st [200005][21] , dp [200005] , s [200005] , t [200005] , aaa [200005] , vis [200005] , ff;
vector < int > gr [200005] , grr [200005] , ss [200005] , tt [200005];
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 go ( int x , int p )
{
    aaa [x] = aaa [p];
    if ( ss [x] . size () || tt [x] . size () ) aaa [x] = x;
    for ( auto u : gr [x] )
    {
        if ( u == p ) continue;
        go ( 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;
        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;
            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;
        long long sum = 0;
        for ( int i = 1 ; i <= m ; i ++ )
        {
            cin >> s [i] >> t [i];
            ss [ s [i] ] . push_back ( i );
            tt [ t [i] ] . push_back ( i );
            int a = lca ( s [i] , t [i] );
        }
        go ( 1 , 0 );
        int num = 0;
        for ( int i = 1 ; i <= m ; i ++ )
        {
            int x = s [i] , y = t [i] , z = lca ( x , y );
            while ( true )
            {
                if ( dp [x] < dp [z] ) break;
                if ( ss [x] . size () )
                {
                    if ( ss [x][0] != i )
                    {
                        grr [i] . push_back ( ss [x][0] );
                        num ++;
                    }
                }
                if ( tt [x] . size () )
                {
                    if ( tt [x][0] != i )
                    {
                        grr [ tt [x][0] ] . push_back ( i );
                        num ++;
                    }
                }
                if ( num > 5 * m ) break;
                if ( x == z ) break;
                x = aaa [ st [x][0] ];
            }
            x = t [i];
            while ( true )
            {
                if ( dp [x] < dp [z] ) break;
                if ( ss [x] . size () )
                {
                    if ( ss [x][0] != i )
                    {
                        grr [i] . push_back ( ss [x][0] );
                        num ++;
                    }
                }
                if ( tt [x] . size () )
                {
                    if ( tt [x][0] != i )
                    {
                        grr [ tt [x][0] ] . push_back ( i );
                        num ++;
                    }
                }
                if ( num > 20 * m ) break;
                if ( x == z ) break;
                x = aaa [ 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
*/

Compilation message

jail.cpp: In function 'int main()':
jail.cpp:106:17: warning: unused variable 'a' [-Wunused-variable]
  106 |             int a = lca ( s [i] , t [i] );
      |                 ^
jail.cpp:100:19: warning: unused variable 'sum' [-Wunused-variable]
  100 |         long long sum = 0;
      |                   ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19092 KB Output is correct
2 Correct 11 ms 19084 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 32 ms 19380 KB Output is correct
5 Correct 59 ms 19332 KB Output is correct
6 Correct 16 ms 19104 KB Output is correct
7 Correct 15 ms 19108 KB Output is correct
8 Correct 17 ms 19232 KB Output is correct
9 Correct 92 ms 20772 KB Output is correct
10 Correct 128 ms 39992 KB Output is correct
11 Correct 27 ms 19236 KB Output is correct
12 Correct 95 ms 19360 KB Output is correct
13 Correct 177 ms 48972 KB Output is correct
14 Correct 168 ms 46532 KB Output is correct
15 Correct 267 ms 49376 KB Output is correct
16 Correct 607 ms 62184 KB Output is correct
17 Correct 182 ms 49060 KB Output is correct
18 Correct 224 ms 52196 KB Output is correct
19 Correct 182 ms 49100 KB Output is correct
20 Incorrect 177 ms 49156 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19028 KB Output is correct
2 Correct 11 ms 19028 KB Output is correct
3 Correct 12 ms 19192 KB Output is correct
4 Correct 15 ms 19148 KB Output is correct
5 Correct 16 ms 19196 KB Output is correct
6 Correct 15 ms 19156 KB Output is correct
7 Correct 13 ms 19192 KB Output is correct
8 Correct 15 ms 19156 KB Output is correct
9 Correct 13 ms 19132 KB Output is correct
10 Correct 15 ms 19076 KB Output is correct
11 Correct 13 ms 19184 KB Output is correct
12 Correct 11 ms 19156 KB Output is correct
13 Correct 11 ms 19108 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19028 KB Output is correct
2 Correct 11 ms 19028 KB Output is correct
3 Correct 12 ms 19192 KB Output is correct
4 Correct 15 ms 19148 KB Output is correct
5 Correct 16 ms 19196 KB Output is correct
6 Correct 15 ms 19156 KB Output is correct
7 Correct 13 ms 19192 KB Output is correct
8 Correct 15 ms 19156 KB Output is correct
9 Correct 13 ms 19132 KB Output is correct
10 Correct 15 ms 19076 KB Output is correct
11 Correct 13 ms 19184 KB Output is correct
12 Correct 11 ms 19156 KB Output is correct
13 Correct 11 ms 19108 KB Output is correct
14 Correct 12 ms 19028 KB Output is correct
15 Correct 12 ms 19100 KB Output is correct
16 Correct 16 ms 19104 KB Output is correct
17 Correct 16 ms 19200 KB Output is correct
18 Correct 14 ms 19168 KB Output is correct
19 Correct 11 ms 19020 KB Output is correct
20 Correct 13 ms 19156 KB Output is correct
21 Correct 13 ms 19156 KB Output is correct
22 Correct 12 ms 19140 KB Output is correct
23 Correct 10 ms 19096 KB Output is correct
24 Correct 12 ms 19132 KB Output is correct
25 Correct 15 ms 19200 KB Output is correct
26 Correct 13 ms 19096 KB Output is correct
27 Correct 12 ms 19108 KB Output is correct
28 Correct 10 ms 19032 KB Output is correct

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19028 KB Output is correct
2 Correct 11 ms 19028 KB Output is correct
3 Correct 12 ms 19192 KB Output is correct
4 Correct 15 ms 19148 KB Output is correct
5 Correct 16 ms 19196 KB Output is correct
6 Correct 15 ms 19156 KB Output is correct
7 Correct 13 ms 19192 KB Output is correct
8 Correct 15 ms 19156 KB Output is correct
9 Correct 13 ms 19132 KB Output is correct
10 Correct 15 ms 19076 KB Output is correct
11 Correct 13 ms 19184 KB Output is correct
12 Correct 11 ms 19156 KB Output is correct
13 Correct 11 ms 19108 KB Output is correct
14 Correct 12 ms 19028 KB Output is correct
15 Correct 12 ms 19100 KB Output is correct
16 Correct 16 ms 19104 KB Output is correct
17 Correct 16 ms 19200 KB Output is correct
18 Correct 14 ms 19168 KB Output is correct
19 Correct 11 ms 19020 KB Output is correct
20 Correct 13 ms 19156 KB Output is correct
21 Correct 13 ms 19156 KB Output is correct
22 Correct 12 ms 19140 KB Output is correct
23 Correct 10 ms 19096 KB Output is correct
24 Correct 12 ms 19132 KB Output is correct
25 Correct 15 ms 19200 KB Output is correct
26 Correct 13 ms 19096 KB Output is correct
27 Correct 12 ms 19108 KB Output is correct
28 Correct 10 ms 19032 KB Output is correct
29 Correct 14 ms 19268 KB Output is correct
30 Correct 13 ms 19104 KB Output is correct
31 Correct 14 ms 19196 KB Output is correct
32 Correct 15 ms 19092 KB Output is correct
33 Correct 12 ms 19104 KB Output is correct
34 Incorrect 17 ms 19216 KB Output isn't correct
35 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19028 KB Output is correct
2 Correct 11 ms 19028 KB Output is correct
3 Correct 12 ms 19192 KB Output is correct
4 Correct 15 ms 19148 KB Output is correct
5 Correct 16 ms 19196 KB Output is correct
6 Correct 15 ms 19156 KB Output is correct
7 Correct 13 ms 19192 KB Output is correct
8 Correct 15 ms 19156 KB Output is correct
9 Correct 13 ms 19132 KB Output is correct
10 Correct 15 ms 19076 KB Output is correct
11 Correct 13 ms 19184 KB Output is correct
12 Correct 11 ms 19156 KB Output is correct
13 Correct 11 ms 19108 KB Output is correct
14 Correct 12 ms 19028 KB Output is correct
15 Correct 12 ms 19100 KB Output is correct
16 Correct 16 ms 19104 KB Output is correct
17 Correct 16 ms 19200 KB Output is correct
18 Correct 14 ms 19168 KB Output is correct
19 Correct 11 ms 19020 KB Output is correct
20 Correct 13 ms 19156 KB Output is correct
21 Correct 13 ms 19156 KB Output is correct
22 Correct 12 ms 19140 KB Output is correct
23 Correct 10 ms 19096 KB Output is correct
24 Correct 12 ms 19132 KB Output is correct
25 Correct 15 ms 19200 KB Output is correct
26 Correct 13 ms 19096 KB Output is correct
27 Correct 12 ms 19108 KB Output is correct
28 Correct 10 ms 19032 KB Output is correct
29 Correct 14 ms 19268 KB Output is correct
30 Correct 13 ms 19104 KB Output is correct
31 Correct 14 ms 19196 KB Output is correct
32 Correct 15 ms 19092 KB Output is correct
33 Correct 12 ms 19104 KB Output is correct
34 Incorrect 17 ms 19216 KB Output isn't correct
35 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19092 KB Output is correct
2 Correct 12 ms 19028 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 12 ms 19096 KB Output is correct
5 Correct 22 ms 19276 KB Output is correct
6 Correct 15 ms 19156 KB Output is correct
7 Correct 13 ms 19156 KB Output is correct
8 Correct 12 ms 19092 KB Output is correct
9 Correct 13 ms 19120 KB Output is correct
10 Correct 13 ms 19104 KB Output is correct
11 Correct 10 ms 19096 KB Output is correct
12 Correct 12 ms 19096 KB Output is correct
13 Correct 51 ms 19428 KB Output is correct
14 Correct 114 ms 19392 KB Output is correct
15 Incorrect 66 ms 19400 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19092 KB Output is correct
2 Correct 11 ms 19084 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 32 ms 19380 KB Output is correct
5 Correct 59 ms 19332 KB Output is correct
6 Correct 16 ms 19104 KB Output is correct
7 Correct 15 ms 19108 KB Output is correct
8 Correct 17 ms 19232 KB Output is correct
9 Correct 92 ms 20772 KB Output is correct
10 Correct 128 ms 39992 KB Output is correct
11 Correct 27 ms 19236 KB Output is correct
12 Correct 95 ms 19360 KB Output is correct
13 Correct 177 ms 48972 KB Output is correct
14 Correct 168 ms 46532 KB Output is correct
15 Correct 267 ms 49376 KB Output is correct
16 Correct 607 ms 62184 KB Output is correct
17 Correct 182 ms 49060 KB Output is correct
18 Correct 224 ms 52196 KB Output is correct
19 Correct 182 ms 49100 KB Output is correct
20 Incorrect 177 ms 49156 KB Output isn't correct
21 Halted 0 ms 0 KB -