oj.uz

Submission #631779

# Submission time Handle Problem Language Result Execution time Memory
631779 2022-08-18T17:32:38 Z mdn2002 Jail (JOI22_jail) C++14
72 / 100
 5000 ms 359472 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 > 600 * 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 > 600 * 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 10 ms 19028 KB Output is correct
3 Correct 11 ms 19028 KB Output is correct
4 Correct 33 ms 19028 KB Output is correct
5 Correct 60 ms 19028 KB Output is correct
6 Correct 13 ms 19156 KB Output is correct
7 Correct 13 ms 19160 KB Output is correct
8 Correct 14 ms 19236 KB Output is correct
9 Correct 109 ms 22320 KB Output is correct
10 Correct 112 ms 41164 KB Output is correct
11 Correct 23 ms 19028 KB Output is correct
12 Correct 84 ms 19216 KB Output is correct
13 Correct 244 ms 72896 KB Output is correct
14 Correct 286 ms 86884 KB Output is correct
15 Correct 2289 ms 184676 KB Output is correct
16 Execution timed out 5096 ms 359472 KB Time limit exceeded
17 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 12 ms 19024 KB Output is correct
3 Correct 13 ms 19168 KB Output is correct
4 Correct 13 ms 19156 KB Output is correct
5 Correct 14 ms 19156 KB Output is correct
6 Correct 13 ms 19120 KB Output is correct
7 Correct 13 ms 19148 KB Output is correct
8 Correct 13 ms 19156 KB Output is correct
9 Correct 13 ms 19156 KB Output is correct
10 Correct 13 ms 19028 KB Output is correct
11 Correct 15 ms 19156 KB Output is correct
12 Correct 11 ms 19028 KB Output is correct
13 Correct 12 ms 19156 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 12 ms 19024 KB Output is correct
3 Correct 13 ms 19168 KB Output is correct
4 Correct 13 ms 19156 KB Output is correct
5 Correct 14 ms 19156 KB Output is correct
6 Correct 13 ms 19120 KB Output is correct
7 Correct 13 ms 19148 KB Output is correct
8 Correct 13 ms 19156 KB Output is correct
9 Correct 13 ms 19156 KB Output is correct
10 Correct 13 ms 19028 KB Output is correct
11 Correct 15 ms 19156 KB Output is correct
12 Correct 11 ms 19028 KB Output is correct
13 Correct 12 ms 19156 KB Output is correct
14 Correct 10 ms 19108 KB Output is correct
15 Correct 11 ms 19072 KB Output is correct
16 Correct 16 ms 19108 KB Output is correct
17 Correct 13 ms 19156 KB Output is correct
18 Correct 13 ms 19156 KB Output is correct
19 Correct 14 ms 19028 KB Output is correct
20 Correct 12 ms 19156 KB Output is correct
21 Correct 13 ms 19156 KB Output is correct
22 Correct 14 ms 19140 KB Output is correct
23 Correct 12 ms 19024 KB Output is correct
24 Correct 11 ms 19064 KB Output is correct
25 Correct 12 ms 19156 KB Output is correct
26 Correct 10 ms 19028 KB Output is correct
27 Correct 12 ms 19100 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 12 ms 19024 KB Output is correct
3 Correct 13 ms 19168 KB Output is correct
4 Correct 13 ms 19156 KB Output is correct
5 Correct 14 ms 19156 KB Output is correct
6 Correct 13 ms 19120 KB Output is correct
7 Correct 13 ms 19148 KB Output is correct
8 Correct 13 ms 19156 KB Output is correct
9 Correct 13 ms 19156 KB Output is correct
10 Correct 13 ms 19028 KB Output is correct
11 Correct 15 ms 19156 KB Output is correct
12 Correct 11 ms 19028 KB Output is correct
13 Correct 12 ms 19156 KB Output is correct
14 Correct 10 ms 19108 KB Output is correct
15 Correct 11 ms 19072 KB Output is correct
16 Correct 16 ms 19108 KB Output is correct
17 Correct 13 ms 19156 KB Output is correct
18 Correct 13 ms 19156 KB Output is correct
19 Correct 14 ms 19028 KB Output is correct
20 Correct 12 ms 19156 KB Output is correct
21 Correct 13 ms 19156 KB Output is correct
22 Correct 14 ms 19140 KB Output is correct
23 Correct 12 ms 19024 KB Output is correct
24 Correct 11 ms 19064 KB Output is correct
25 Correct 12 ms 19156 KB Output is correct
26 Correct 10 ms 19028 KB Output is correct
27 Correct 12 ms 19100 KB Output is correct
28 Correct 10 ms 19028 KB Output is correct
29 Correct 14 ms 19144 KB Output is correct
30 Correct 16 ms 19076 KB Output is correct
31 Correct 14 ms 19156 KB Output is correct
32 Correct 17 ms 19156 KB Output is correct
33 Correct 16 ms 19156 KB Output is correct
34 Correct 16 ms 19180 KB Output is correct
35 Correct 14 ms 19156 KB Output is correct
36 Correct 13 ms 19156 KB Output is correct
37 Correct 12 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 12 ms 19024 KB Output is correct
3 Correct 13 ms 19168 KB Output is correct
4 Correct 13 ms 19156 KB Output is correct
5 Correct 14 ms 19156 KB Output is correct
6 Correct 13 ms 19120 KB Output is correct
7 Correct 13 ms 19148 KB Output is correct
8 Correct 13 ms 19156 KB Output is correct
9 Correct 13 ms 19156 KB Output is correct
10 Correct 13 ms 19028 KB Output is correct
11 Correct 15 ms 19156 KB Output is correct
12 Correct 11 ms 19028 KB Output is correct
13 Correct 12 ms 19156 KB Output is correct
14 Correct 10 ms 19108 KB Output is correct
15 Correct 11 ms 19072 KB Output is correct
16 Correct 16 ms 19108 KB Output is correct
17 Correct 13 ms 19156 KB Output is correct
18 Correct 13 ms 19156 KB Output is correct
19 Correct 14 ms 19028 KB Output is correct
20 Correct 12 ms 19156 KB Output is correct
21 Correct 13 ms 19156 KB Output is correct
22 Correct 14 ms 19140 KB Output is correct
23 Correct 12 ms 19024 KB Output is correct
24 Correct 11 ms 19064 KB Output is correct
25 Correct 12 ms 19156 KB Output is correct
26 Correct 10 ms 19028 KB Output is correct
27 Correct 12 ms 19100 KB Output is correct
28 Correct 10 ms 19028 KB Output is correct
29 Correct 14 ms 19144 KB Output is correct
30 Correct 16 ms 19076 KB Output is correct
31 Correct 14 ms 19156 KB Output is correct
32 Correct 17 ms 19156 KB Output is correct
33 Correct 16 ms 19156 KB Output is correct
34 Correct 16 ms 19180 KB Output is correct
35 Correct 14 ms 19156 KB Output is correct
36 Correct 13 ms 19156 KB Output is correct
37 Correct 12 ms 19156 KB Output is correct
38 Correct 106 ms 22296 KB Output is correct
39 Correct 107 ms 41036 KB Output is correct
40 Correct 106 ms 21276 KB Output is correct
41 Correct 86 ms 20100 KB Output is correct
42 Correct 87 ms 21524 KB Output is correct
43 Correct 89 ms 19984 KB Output is correct
44 Correct 26 ms 19412 KB Output is correct
45 Correct 126 ms 34120 KB Output is correct
46 Correct 140 ms 34208 KB Output is correct
47 Correct 115 ms 36868 KB Output is correct
48 Correct 106 ms 36924 KB Output is correct
49 Correct 119 ms 34240 KB Output is correct
50 Correct 116 ms 34248 KB Output is correct
51 Correct 125 ms 35060 KB Output is correct
52 Correct 113 ms 35020 KB Output is correct
53 Correct 30 ms 20200 KB Output is correct
54 Correct 136 ms 34164 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 19028 KB Output is correct
3 Correct 11 ms 19060 KB Output is correct
4 Correct 11 ms 19028 KB Output is correct
5 Correct 26 ms 19136 KB Output is correct
6 Correct 12 ms 19156 KB Output is correct
7 Correct 11 ms 19052 KB Output is correct
8 Correct 11 ms 19028 KB Output is correct
9 Correct 10 ms 19028 KB Output is correct
10 Correct 10 ms 19028 KB Output is correct
11 Correct 11 ms 19028 KB Output is correct
12 Correct 12 ms 19144 KB Output is correct
13 Correct 56 ms 19152 KB Output is correct
14 Correct 74 ms 19132 KB Output is correct
15 Correct 61 ms 19172 KB Output is correct
16 Correct 137 ms 35300 KB Output is correct
17 Correct 311 ms 44852 KB Output is correct
18 Correct 733 ms 71956 KB Output is correct
19 Correct 157 ms 35916 KB Output is correct
20 Correct 156 ms 36012 KB Output is correct
21 Correct 155 ms 35912 KB Output is correct
22 Correct 294 ms 45268 KB Output is correct
23 Correct 241 ms 45000 KB Output is correct
24 Correct 243 ms 45056 KB Output is correct
25 Correct 235 ms 45224 KB Output is correct
26 Correct 228 ms 45140 KB Output is correct
27 Correct 349 ms 51012 KB Output is correct
28 Correct 328 ms 52420 KB Output is correct
29 Correct 338 ms 49560 KB Output is correct
30 Correct 258 ms 42780 KB Output is correct
31 Correct 217 ms 43216 KB Output is correct
32 Correct 269 ms 42568 KB Output is correct
33 Correct 250 ms 43248 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 11 ms 19028 KB Output is correct
4 Correct 33 ms 19028 KB Output is correct
5 Correct 60 ms 19028 KB Output is correct
6 Correct 13 ms 19156 KB Output is correct
7 Correct 13 ms 19160 KB Output is correct
8 Correct 14 ms 19236 KB Output is correct
9 Correct 109 ms 22320 KB Output is correct
10 Correct 112 ms 41164 KB Output is correct
11 Correct 23 ms 19028 KB Output is correct
12 Correct 84 ms 19216 KB Output is correct
13 Correct 244 ms 72896 KB Output is correct
14 Correct 286 ms 86884 KB Output is correct
15 Correct 2289 ms 184676 KB Output is correct
16 Execution timed out 5096 ms 359472 KB Time limit exceeded
17 Halted 0 ms 0 KB -