oj.uz

Submission #631381

# Submission time Handle Problem Language Result Execution time Memory
631381 2022-08-18T04:36:25 Z mdn2002 Jail (JOI22_jail) C++14
72 / 100
 5000 ms 347116 KB 
#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];
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;
        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;
        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 ( 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.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 10 ms 19028 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 30 ms 19072 KB Output is correct
5 Correct 55 ms 19036 KB Output is correct
6 Correct 11 ms 19156 KB Output is correct
7 Correct 14 ms 19156 KB Output is correct
8 Correct 27 ms 19236 KB Output is correct
9 Correct 467 ms 22252 KB Output is correct
10 Correct 145 ms 40628 KB Output is correct
11 Correct 27 ms 19028 KB Output is correct
12 Correct 281 ms 19156 KB Output is correct
13 Correct 248 ms 72524 KB Output is correct
14 Correct 293 ms 88360 KB Output is correct
15 Execution timed out 5099 ms 347116 KB Time limit exceeded
16 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 19040 KB Output is correct
3 Correct 12 ms 19156 KB Output is correct
4 Correct 14 ms 19156 KB Output is correct
5 Correct 12 ms 19156 KB Output is correct
6 Correct 12 ms 19132 KB Output is correct
7 Correct 11 ms 19156 KB Output is correct
8 Correct 12 ms 19156 KB Output is correct
9 Correct 12 ms 19156 KB Output is correct
10 Correct 12 ms 19156 KB Output is correct
11 Correct 12 ms 19156 KB Output is correct
12 Correct 13 ms 19156 KB Output is correct
13 Correct 14 ms 19028 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 19040 KB Output is correct
3 Correct 12 ms 19156 KB Output is correct
4 Correct 14 ms 19156 KB Output is correct
5 Correct 12 ms 19156 KB Output is correct
6 Correct 12 ms 19132 KB Output is correct
7 Correct 11 ms 19156 KB Output is correct
8 Correct 12 ms 19156 KB Output is correct
9 Correct 12 ms 19156 KB Output is correct
10 Correct 12 ms 19156 KB Output is correct
11 Correct 12 ms 19156 KB Output is correct
12 Correct 13 ms 19156 KB Output is correct
13 Correct 14 ms 19028 KB Output is correct
14 Correct 10 ms 19092 KB Output is correct
15 Correct 12 ms 19080 KB Output is correct
16 Correct 12 ms 19100 KB Output is correct
17 Correct 12 ms 19156 KB Output is correct
18 Correct 12 ms 19164 KB Output is correct
19 Correct 10 ms 19008 KB Output is correct
20 Correct 13 ms 19156 KB Output is correct
21 Correct 14 ms 19156 KB Output is correct
22 Correct 12 ms 19156 KB Output is correct
23 Correct 10 ms 19056 KB Output is correct
24 Correct 12 ms 19052 KB Output is correct
25 Correct 12 ms 19156 KB Output is correct
26 Correct 11 ms 19040 KB Output is correct
27 Correct 12 ms 19156 KB Output is correct
28 Correct 10 ms 19028 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 19040 KB Output is correct
3 Correct 12 ms 19156 KB Output is correct
4 Correct 14 ms 19156 KB Output is correct
5 Correct 12 ms 19156 KB Output is correct
6 Correct 12 ms 19132 KB Output is correct
7 Correct 11 ms 19156 KB Output is correct
8 Correct 12 ms 19156 KB Output is correct
9 Correct 12 ms 19156 KB Output is correct
10 Correct 12 ms 19156 KB Output is correct
11 Correct 12 ms 19156 KB Output is correct
12 Correct 13 ms 19156 KB Output is correct
13 Correct 14 ms 19028 KB Output is correct
14 Correct 10 ms 19092 KB Output is correct
15 Correct 12 ms 19080 KB Output is correct
16 Correct 12 ms 19100 KB Output is correct
17 Correct 12 ms 19156 KB Output is correct
18 Correct 12 ms 19164 KB Output is correct
19 Correct 10 ms 19008 KB Output is correct
20 Correct 13 ms 19156 KB Output is correct
21 Correct 14 ms 19156 KB Output is correct
22 Correct 12 ms 19156 KB Output is correct
23 Correct 10 ms 19056 KB Output is correct
24 Correct 12 ms 19052 KB Output is correct
25 Correct 12 ms 19156 KB Output is correct
26 Correct 11 ms 19040 KB Output is correct
27 Correct 12 ms 19156 KB Output is correct
28 Correct 10 ms 19028 KB Output is correct
29 Correct 27 ms 19156 KB Output is correct
30 Correct 42 ms 19156 KB Output is correct
31 Correct 27 ms 19192 KB Output is correct
32 Correct 21 ms 19104 KB Output is correct
33 Correct 14 ms 19156 KB Output is correct
34 Correct 79 ms 19112 KB Output is correct
35 Correct 74 ms 19212 KB Output is correct
36 Correct 70 ms 19144 KB Output is correct
37 Correct 35 ms 19288 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 19040 KB Output is correct
3 Correct 12 ms 19156 KB Output is correct
4 Correct 14 ms 19156 KB Output is correct
5 Correct 12 ms 19156 KB Output is correct
6 Correct 12 ms 19132 KB Output is correct
7 Correct 11 ms 19156 KB Output is correct
8 Correct 12 ms 19156 KB Output is correct
9 Correct 12 ms 19156 KB Output is correct
10 Correct 12 ms 19156 KB Output is correct
11 Correct 12 ms 19156 KB Output is correct
12 Correct 13 ms 19156 KB Output is correct
13 Correct 14 ms 19028 KB Output is correct
14 Correct 10 ms 19092 KB Output is correct
15 Correct 12 ms 19080 KB Output is correct
16 Correct 12 ms 19100 KB Output is correct
17 Correct 12 ms 19156 KB Output is correct
18 Correct 12 ms 19164 KB Output is correct
19 Correct 10 ms 19008 KB Output is correct
20 Correct 13 ms 19156 KB Output is correct
21 Correct 14 ms 19156 KB Output is correct
22 Correct 12 ms 19156 KB Output is correct
23 Correct 10 ms 19056 KB Output is correct
24 Correct 12 ms 19052 KB Output is correct
25 Correct 12 ms 19156 KB Output is correct
26 Correct 11 ms 19040 KB Output is correct
27 Correct 12 ms 19156 KB Output is correct
28 Correct 10 ms 19028 KB Output is correct
29 Correct 27 ms 19156 KB Output is correct
30 Correct 42 ms 19156 KB Output is correct
31 Correct 27 ms 19192 KB Output is correct
32 Correct 21 ms 19104 KB Output is correct
33 Correct 14 ms 19156 KB Output is correct
34 Correct 79 ms 19112 KB Output is correct
35 Correct 74 ms 19212 KB Output is correct
36 Correct 70 ms 19144 KB Output is correct
37 Correct 35 ms 19288 KB Output is correct
38 Correct 468 ms 22264 KB Output is correct
39 Correct 142 ms 40560 KB Output is correct
40 Correct 1355 ms 21328 KB Output is correct
41 Correct 1640 ms 20172 KB Output is correct
42 Correct 1942 ms 21500 KB Output is correct
43 Correct 77 ms 19924 KB Output is correct
44 Correct 1663 ms 19556 KB Output is correct
45 Correct 231 ms 33736 KB Output is correct
46 Correct 230 ms 33656 KB Output is correct
47 Correct 209 ms 36448 KB Output is correct
48 Correct 220 ms 36428 KB Output is correct
49 Correct 210 ms 33856 KB Output is correct
50 Correct 197 ms 34044 KB Output is correct
51 Correct 110 ms 34584 KB Output is correct
52 Correct 108 ms 34588 KB Output is correct
53 Correct 1377 ms 20328 KB Output is correct
54 Correct 214 ms 33672 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 10 ms 19004 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 10 ms 19048 KB Output is correct
5 Correct 27 ms 19028 KB Output is correct
6 Correct 12 ms 19096 KB Output is correct
7 Correct 11 ms 19044 KB Output is correct
8 Correct 11 ms 19028 KB Output is correct
9 Correct 11 ms 19056 KB Output is correct
10 Correct 12 ms 19028 KB Output is correct
11 Correct 10 ms 19028 KB Output is correct
12 Correct 67 ms 19152 KB Output is correct
13 Correct 659 ms 19176 KB Output is correct
14 Correct 333 ms 19148 KB Output is correct
15 Correct 543 ms 19156 KB Output is correct
16 Correct 127 ms 34776 KB Output is correct
17 Correct 283 ms 44288 KB Output is correct
18 Correct 677 ms 71352 KB Output is correct
19 Correct 143 ms 35404 KB Output is correct
20 Correct 146 ms 37168 KB Output is correct
21 Correct 154 ms 37016 KB Output is correct
22 Correct 256 ms 46800 KB Output is correct
23 Correct 221 ms 46636 KB Output is correct
24 Correct 223 ms 46672 KB Output is correct
25 Correct 220 ms 46844 KB Output is correct
26 Correct 231 ms 46896 KB Output is correct
27 Correct 330 ms 53432 KB Output is correct
28 Correct 321 ms 54756 KB Output is correct
29 Correct 336 ms 51872 KB Output is correct
30 Correct 201 ms 44464 KB Output is correct
31 Correct 215 ms 44932 KB Output is correct
32 Correct 206 ms 44312 KB Output is correct
33 Correct 199 ms 44916 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 10 ms 19028 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 30 ms 19072 KB Output is correct
5 Correct 55 ms 19036 KB Output is correct
6 Correct 11 ms 19156 KB Output is correct
7 Correct 14 ms 19156 KB Output is correct
8 Correct 27 ms 19236 KB Output is correct
9 Correct 467 ms 22252 KB Output is correct
10 Correct 145 ms 40628 KB Output is correct
11 Correct 27 ms 19028 KB Output is correct
12 Correct 281 ms 19156 KB Output is correct
13 Correct 248 ms 72524 KB Output is correct
14 Correct 293 ms 88360 KB Output is correct
15 Execution timed out 5099 ms 347116 KB Time limit exceeded
16 Halted 0 ms 0 KB -