oj.uz

Submission #631778

# Submission time Handle Problem Language Result Execution time Memory
631778 2022-08-18T17:32:01 Z mdn2002 Jail (JOI22_jail) C++14
72 / 100
 5000 ms 344360 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 > 1000 * 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 > 1000 * 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 11 ms 19028 KB Output is correct
2 Correct 12 ms 19028 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 33 ms 19028 KB Output is correct
5 Correct 55 ms 19028 KB Output is correct
6 Correct 15 ms 19156 KB Output is correct
7 Correct 12 ms 19156 KB Output is correct
8 Correct 15 ms 19156 KB Output is correct
9 Correct 109 ms 22268 KB Output is correct
10 Correct 108 ms 41136 KB Output is correct
11 Correct 23 ms 19028 KB Output is correct
12 Correct 90 ms 19292 KB Output is correct
13 Correct 242 ms 72908 KB Output is correct
14 Correct 269 ms 86860 KB Output is correct
15 Correct 3731 ms 293968 KB Output is correct
16 Execution timed out 5093 ms 344360 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 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 14 ms 19156 KB Output is correct
6 Correct 12 ms 19028 KB Output is correct
7 Correct 12 ms 19144 KB Output is correct
8 Correct 13 ms 19152 KB Output is correct
9 Correct 12 ms 19060 KB Output is correct
10 Correct 13 ms 19076 KB Output is correct
11 Correct 15 ms 19152 KB Output is correct
12 Correct 13 ms 19136 KB Output is correct
13 Correct 12 ms 19028 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 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 14 ms 19156 KB Output is correct
6 Correct 12 ms 19028 KB Output is correct
7 Correct 12 ms 19144 KB Output is correct
8 Correct 13 ms 19152 KB Output is correct
9 Correct 12 ms 19060 KB Output is correct
10 Correct 13 ms 19076 KB Output is correct
11 Correct 15 ms 19152 KB Output is correct
12 Correct 13 ms 19136 KB Output is correct
13 Correct 12 ms 19028 KB Output is correct
14 Correct 11 ms 19028 KB Output is correct
15 Correct 13 ms 19028 KB Output is correct
16 Correct 13 ms 19156 KB Output is correct
17 Correct 12 ms 19156 KB Output is correct
18 Correct 12 ms 19164 KB Output is correct
19 Correct 11 ms 19028 KB Output is correct
20 Correct 12 ms 19156 KB Output is correct
21 Correct 12 ms 19156 KB Output is correct
22 Correct 15 ms 19104 KB Output is correct
23 Correct 11 ms 19044 KB Output is correct
24 Correct 13 ms 19032 KB Output is correct
25 Correct 13 ms 19148 KB Output is correct
26 Correct 11 ms 19092 KB Output is correct
27 Correct 13 ms 19156 KB Output is correct
28 Correct 12 ms 19048 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 9 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 14 ms 19156 KB Output is correct
6 Correct 12 ms 19028 KB Output is correct
7 Correct 12 ms 19144 KB Output is correct
8 Correct 13 ms 19152 KB Output is correct
9 Correct 12 ms 19060 KB Output is correct
10 Correct 13 ms 19076 KB Output is correct
11 Correct 15 ms 19152 KB Output is correct
12 Correct 13 ms 19136 KB Output is correct
13 Correct 12 ms 19028 KB Output is correct
14 Correct 11 ms 19028 KB Output is correct
15 Correct 13 ms 19028 KB Output is correct
16 Correct 13 ms 19156 KB Output is correct
17 Correct 12 ms 19156 KB Output is correct
18 Correct 12 ms 19164 KB Output is correct
19 Correct 11 ms 19028 KB Output is correct
20 Correct 12 ms 19156 KB Output is correct
21 Correct 12 ms 19156 KB Output is correct
22 Correct 15 ms 19104 KB Output is correct
23 Correct 11 ms 19044 KB Output is correct
24 Correct 13 ms 19032 KB Output is correct
25 Correct 13 ms 19148 KB Output is correct
26 Correct 11 ms 19092 KB Output is correct
27 Correct 13 ms 19156 KB Output is correct
28 Correct 12 ms 19048 KB Output is correct
29 Correct 15 ms 19156 KB Output is correct
30 Correct 13 ms 19168 KB Output is correct
31 Correct 13 ms 19172 KB Output is correct
32 Correct 12 ms 19156 KB Output is correct
33 Correct 15 ms 19156 KB Output is correct
34 Correct 13 ms 19148 KB Output is correct
35 Correct 14 ms 19156 KB Output is correct
36 Correct 12 ms 19156 KB Output is correct
37 Correct 11 ms 19080 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 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 14 ms 19156 KB Output is correct
6 Correct 12 ms 19028 KB Output is correct
7 Correct 12 ms 19144 KB Output is correct
8 Correct 13 ms 19152 KB Output is correct
9 Correct 12 ms 19060 KB Output is correct
10 Correct 13 ms 19076 KB Output is correct
11 Correct 15 ms 19152 KB Output is correct
12 Correct 13 ms 19136 KB Output is correct
13 Correct 12 ms 19028 KB Output is correct
14 Correct 11 ms 19028 KB Output is correct
15 Correct 13 ms 19028 KB Output is correct
16 Correct 13 ms 19156 KB Output is correct
17 Correct 12 ms 19156 KB Output is correct
18 Correct 12 ms 19164 KB Output is correct
19 Correct 11 ms 19028 KB Output is correct
20 Correct 12 ms 19156 KB Output is correct
21 Correct 12 ms 19156 KB Output is correct
22 Correct 15 ms 19104 KB Output is correct
23 Correct 11 ms 19044 KB Output is correct
24 Correct 13 ms 19032 KB Output is correct
25 Correct 13 ms 19148 KB Output is correct
26 Correct 11 ms 19092 KB Output is correct
27 Correct 13 ms 19156 KB Output is correct
28 Correct 12 ms 19048 KB Output is correct
29 Correct 15 ms 19156 KB Output is correct
30 Correct 13 ms 19168 KB Output is correct
31 Correct 13 ms 19172 KB Output is correct
32 Correct 12 ms 19156 KB Output is correct
33 Correct 15 ms 19156 KB Output is correct
34 Correct 13 ms 19148 KB Output is correct
35 Correct 14 ms 19156 KB Output is correct
36 Correct 12 ms 19156 KB Output is correct
37 Correct 11 ms 19080 KB Output is correct
38 Correct 106 ms 22192 KB Output is correct
39 Correct 107 ms 41108 KB Output is correct
40 Correct 93 ms 21324 KB Output is correct
41 Correct 81 ms 20160 KB Output is correct
42 Correct 81 ms 21480 KB Output is correct
43 Correct 71 ms 20016 KB Output is correct
44 Correct 33 ms 19488 KB Output is correct
45 Correct 153 ms 34184 KB Output is correct
46 Correct 120 ms 34112 KB Output is correct
47 Correct 104 ms 36936 KB Output is correct
48 Correct 106 ms 36924 KB Output is correct
49 Correct 124 ms 34264 KB Output is correct
50 Correct 123 ms 34264 KB Output is correct
51 Correct 135 ms 35056 KB Output is correct
52 Correct 112 ms 35040 KB Output is correct
53 Correct 32 ms 20284 KB Output is correct
54 Correct 164 ms 34184 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 10 ms 19020 KB Output is correct
4 Correct 11 ms 19028 KB Output is correct
5 Correct 24 ms 19128 KB Output is correct
6 Correct 11 ms 19156 KB Output is correct
7 Correct 12 ms 19064 KB Output is correct
8 Correct 12 ms 19028 KB Output is correct
9 Correct 11 ms 19044 KB Output is correct
10 Correct 10 ms 19028 KB Output is correct
11 Correct 10 ms 19028 KB Output is correct
12 Correct 13 ms 19172 KB Output is correct
13 Correct 49 ms 19148 KB Output is correct
14 Correct 69 ms 19148 KB Output is correct
15 Correct 59 ms 19156 KB Output is correct
16 Correct 146 ms 35252 KB Output is correct
17 Correct 314 ms 44832 KB Output is correct
18 Correct 701 ms 71852 KB Output is correct
19 Correct 161 ms 35916 KB Output is correct
20 Correct 147 ms 36076 KB Output is correct
21 Correct 156 ms 35916 KB Output is correct
22 Correct 291 ms 45204 KB Output is correct
23 Correct 264 ms 45024 KB Output is correct
24 Correct 247 ms 45036 KB Output is correct
25 Correct 248 ms 45320 KB Output is correct
26 Correct 229 ms 45104 KB Output is correct
27 Correct 326 ms 51008 KB Output is correct
28 Correct 325 ms 52464 KB Output is correct
29 Correct 374 ms 49476 KB Output is correct
30 Correct 216 ms 42716 KB Output is correct
31 Correct 222 ms 43248 KB Output is correct
32 Correct 253 ms 42644 KB Output is correct
33 Correct 229 ms 43208 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19028 KB Output is correct
2 Correct 12 ms 19028 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 33 ms 19028 KB Output is correct
5 Correct 55 ms 19028 KB Output is correct
6 Correct 15 ms 19156 KB Output is correct
7 Correct 12 ms 19156 KB Output is correct
8 Correct 15 ms 19156 KB Output is correct
9 Correct 109 ms 22268 KB Output is correct
10 Correct 108 ms 41136 KB Output is correct
11 Correct 23 ms 19028 KB Output is correct
12 Correct 90 ms 19292 KB Output is correct
13 Correct 242 ms 72908 KB Output is correct
14 Correct 269 ms 86860 KB Output is correct
15 Correct 3731 ms 293968 KB Output is correct
16 Execution timed out 5093 ms 344360 KB Time limit exceeded
17 Halted 0 ms 0 KB -