oj.uz

Submission #631780

# Submission time Handle Problem Language Result Execution time Memory
631780 2022-08-18T17:33:09 Z mdn2002 Jail (JOI22_jail) C++14
72 / 100
 3296 ms 219872 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;
            aaa [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 > 300 * 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 > 300 * 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:107:17: warning: unused variable 'a' [-Wunused-variable]
  107 |             int a = lca ( s [i] , t [i] );
      |                 ^
jail.cpp:101:19: warning: unused variable 'sum' [-Wunused-variable]
  101 |         long long sum = 0;
      |                   ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 12 ms 19028 KB Output is correct
3 Correct 11 ms 19032 KB Output is correct
4 Correct 34 ms 19028 KB Output is correct
5 Correct 62 ms 19140 KB Output is correct
6 Correct 12 ms 19156 KB Output is correct
7 Correct 13 ms 19156 KB Output is correct
8 Correct 14 ms 19156 KB Output is correct
9 Correct 103 ms 22004 KB Output is correct
10 Correct 107 ms 40652 KB Output is correct
11 Correct 27 ms 19020 KB Output is correct
12 Correct 89 ms 19220 KB Output is correct
13 Correct 230 ms 72900 KB Output is correct
14 Correct 268 ms 86860 KB Output is correct
15 Correct 1180 ms 114556 KB Output is correct
16 Correct 3296 ms 219872 KB Output is correct
17 Correct 433 ms 115080 KB Output is correct
18 Correct 208 ms 51964 KB Output is correct
19 Correct 321 ms 116392 KB Output is correct
20 Incorrect 329 ms 116536 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 10 ms 19028 KB Output is correct
2 Correct 11 ms 19028 KB Output is correct
3 Correct 12 ms 19156 KB Output is correct
4 Correct 12 ms 19156 KB Output is correct
5 Correct 13 ms 19156 KB Output is correct
6 Correct 16 ms 19156 KB Output is correct
7 Correct 13 ms 19152 KB Output is correct
8 Correct 12 ms 19064 KB Output is correct
9 Correct 12 ms 19028 KB Output is correct
10 Correct 13 ms 19104 KB Output is correct
11 Correct 12 ms 19156 KB Output is correct
12 Correct 11 ms 19152 KB Output is correct
13 Correct 11 ms 19116 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 11 ms 19028 KB Output is correct
3 Correct 12 ms 19156 KB Output is correct
4 Correct 12 ms 19156 KB Output is correct
5 Correct 13 ms 19156 KB Output is correct
6 Correct 16 ms 19156 KB Output is correct
7 Correct 13 ms 19152 KB Output is correct
8 Correct 12 ms 19064 KB Output is correct
9 Correct 12 ms 19028 KB Output is correct
10 Correct 13 ms 19104 KB Output is correct
11 Correct 12 ms 19156 KB Output is correct
12 Correct 11 ms 19152 KB Output is correct
13 Correct 11 ms 19116 KB Output is correct
14 Correct 10 ms 19028 KB Output is correct
15 Correct 10 ms 18996 KB Output is correct
16 Correct 13 ms 19160 KB Output is correct
17 Correct 13 ms 19156 KB Output is correct
18 Correct 13 ms 19160 KB Output is correct
19 Correct 11 ms 19016 KB Output is correct
20 Correct 13 ms 19072 KB Output is correct
21 Correct 12 ms 19156 KB Output is correct
22 Correct 13 ms 19064 KB Output is correct
23 Correct 11 ms 19120 KB Output is correct
24 Correct 11 ms 19028 KB Output is correct
25 Correct 12 ms 19156 KB Output is correct
26 Correct 10 ms 19156 KB Output is correct
27 Correct 13 ms 19156 KB Output is correct
28 Correct 11 ms 19284 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 11 ms 19028 KB Output is correct
3 Correct 12 ms 19156 KB Output is correct
4 Correct 12 ms 19156 KB Output is correct
5 Correct 13 ms 19156 KB Output is correct
6 Correct 16 ms 19156 KB Output is correct
7 Correct 13 ms 19152 KB Output is correct
8 Correct 12 ms 19064 KB Output is correct
9 Correct 12 ms 19028 KB Output is correct
10 Correct 13 ms 19104 KB Output is correct
11 Correct 12 ms 19156 KB Output is correct
12 Correct 11 ms 19152 KB Output is correct
13 Correct 11 ms 19116 KB Output is correct
14 Correct 10 ms 19028 KB Output is correct
15 Correct 10 ms 18996 KB Output is correct
16 Correct 13 ms 19160 KB Output is correct
17 Correct 13 ms 19156 KB Output is correct
18 Correct 13 ms 19160 KB Output is correct
19 Correct 11 ms 19016 KB Output is correct
20 Correct 13 ms 19072 KB Output is correct
21 Correct 12 ms 19156 KB Output is correct
22 Correct 13 ms 19064 KB Output is correct
23 Correct 11 ms 19120 KB Output is correct
24 Correct 11 ms 19028 KB Output is correct
25 Correct 12 ms 19156 KB Output is correct
26 Correct 10 ms 19156 KB Output is correct
27 Correct 13 ms 19156 KB Output is correct
28 Correct 11 ms 19284 KB Output is correct
29 Correct 18 ms 19224 KB Output is correct
30 Correct 14 ms 19156 KB Output is correct
31 Correct 13 ms 19156 KB Output is correct
32 Correct 13 ms 19156 KB Output is correct
33 Correct 12 ms 19156 KB Output is correct
34 Correct 13 ms 19156 KB Output is correct
35 Correct 14 ms 19156 KB Output is correct
36 Correct 16 ms 19156 KB Output is correct
37 Correct 13 ms 19156 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 11 ms 19028 KB Output is correct
3 Correct 12 ms 19156 KB Output is correct
4 Correct 12 ms 19156 KB Output is correct
5 Correct 13 ms 19156 KB Output is correct
6 Correct 16 ms 19156 KB Output is correct
7 Correct 13 ms 19152 KB Output is correct
8 Correct 12 ms 19064 KB Output is correct
9 Correct 12 ms 19028 KB Output is correct
10 Correct 13 ms 19104 KB Output is correct
11 Correct 12 ms 19156 KB Output is correct
12 Correct 11 ms 19152 KB Output is correct
13 Correct 11 ms 19116 KB Output is correct
14 Correct 10 ms 19028 KB Output is correct
15 Correct 10 ms 18996 KB Output is correct
16 Correct 13 ms 19160 KB Output is correct
17 Correct 13 ms 19156 KB Output is correct
18 Correct 13 ms 19160 KB Output is correct
19 Correct 11 ms 19016 KB Output is correct
20 Correct 13 ms 19072 KB Output is correct
21 Correct 12 ms 19156 KB Output is correct
22 Correct 13 ms 19064 KB Output is correct
23 Correct 11 ms 19120 KB Output is correct
24 Correct 11 ms 19028 KB Output is correct
25 Correct 12 ms 19156 KB Output is correct
26 Correct 10 ms 19156 KB Output is correct
27 Correct 13 ms 19156 KB Output is correct
28 Correct 11 ms 19284 KB Output is correct
29 Correct 18 ms 19224 KB Output is correct
30 Correct 14 ms 19156 KB Output is correct
31 Correct 13 ms 19156 KB Output is correct
32 Correct 13 ms 19156 KB Output is correct
33 Correct 12 ms 19156 KB Output is correct
34 Correct 13 ms 19156 KB Output is correct
35 Correct 14 ms 19156 KB Output is correct
36 Correct 16 ms 19156 KB Output is correct
37 Correct 13 ms 19156 KB Output is correct
38 Correct 118 ms 21900 KB Output is correct
39 Correct 105 ms 40692 KB Output is correct
40 Correct 99 ms 21228 KB Output is correct
41 Correct 78 ms 20156 KB Output is correct
42 Correct 85 ms 21508 KB Output is correct
43 Correct 71 ms 19992 KB Output is correct
44 Correct 25 ms 19432 KB Output is correct
45 Correct 124 ms 34208 KB Output is correct
46 Correct 130 ms 34184 KB Output is correct
47 Correct 106 ms 36904 KB Output is correct
48 Correct 129 ms 36936 KB Output is correct
49 Correct 117 ms 34272 KB Output is correct
50 Correct 125 ms 34312 KB Output is correct
51 Correct 103 ms 35072 KB Output is correct
52 Correct 105 ms 35020 KB Output is correct
53 Correct 31 ms 20268 KB Output is correct
54 Correct 140 ms 34112 KB Output is correct

Subtask #6
11.0 / 11.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 11 ms 19028 KB Output is correct
4 Correct 10 ms 19040 KB Output is correct
5 Correct 22 ms 19140 KB Output is correct
6 Correct 11 ms 19028 KB Output is correct
7 Correct 11 ms 19028 KB Output is correct
8 Correct 10 ms 19112 KB Output is correct
9 Correct 11 ms 19028 KB Output is correct
10 Correct 11 ms 19028 KB Output is correct
11 Correct 10 ms 19028 KB Output is correct
12 Correct 15 ms 19160 KB Output is correct
13 Correct 50 ms 19204 KB Output is correct
14 Correct 70 ms 19132 KB Output is correct
15 Correct 59 ms 19156 KB Output is correct
16 Correct 141 ms 35208 KB Output is correct
17 Correct 354 ms 44932 KB Output is correct
18 Correct 692 ms 71864 KB Output is correct
19 Correct 152 ms 35916 KB Output is correct
20 Correct 148 ms 36044 KB Output is correct
21 Correct 149 ms 35920 KB Output is correct
22 Correct 279 ms 45136 KB Output is correct
23 Correct 228 ms 44944 KB Output is correct
24 Correct 224 ms 45048 KB Output is correct
25 Correct 232 ms 45236 KB Output is correct
26 Correct 230 ms 45172 KB Output is correct
27 Correct 344 ms 51032 KB Output is correct
28 Correct 334 ms 52496 KB Output is correct
29 Correct 325 ms 49600 KB Output is correct
30 Correct 232 ms 42848 KB Output is correct
31 Correct 215 ms 43300 KB Output is correct
32 Correct 243 ms 42584 KB Output is correct
33 Correct 213 ms 43224 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 12 ms 19028 KB Output is correct
3 Correct 11 ms 19032 KB Output is correct
4 Correct 34 ms 19028 KB Output is correct
5 Correct 62 ms 19140 KB Output is correct
6 Correct 12 ms 19156 KB Output is correct
7 Correct 13 ms 19156 KB Output is correct
8 Correct 14 ms 19156 KB Output is correct
9 Correct 103 ms 22004 KB Output is correct
10 Correct 107 ms 40652 KB Output is correct
11 Correct 27 ms 19020 KB Output is correct
12 Correct 89 ms 19220 KB Output is correct
13 Correct 230 ms 72900 KB Output is correct
14 Correct 268 ms 86860 KB Output is correct
15 Correct 1180 ms 114556 KB Output is correct
16 Correct 3296 ms 219872 KB Output is correct
17 Correct 433 ms 115080 KB Output is correct
18 Correct 208 ms 51964 KB Output is correct
19 Correct 321 ms 116392 KB Output is correct
20 Incorrect 329 ms 116536 KB Output isn't correct
21 Halted 0 ms 0 KB -