| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 631507 |
2022-08-18T08:02:12 Z |
mdn2002 |
Jail (JOI22_jail) |
C++14 |
|
37 ms |
19156 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];
int tree [800005];
void up ( int nod , int l , int r , int x , int val )
{
if ( x < l || r < x ) return;
if ( l == r )
{
tree [nod] += val;
return;
}
int mid = ( l + r ) / 2;
up ( nod * 2 , l , mid , x , val );
up ( nod * 2 + 1 , mid + 1 , r , x , val );
tree [nod] = tree [ nod * 2 ] + tree [ nod * 2 + 1 ];
}
long long qr ( int nod , int l , int r , int x , int y )
{
if ( y < l || r < x ) return 0;
if ( x <= l && r <= y ) return tree [nod];
int mid = ( l + r ) / 2;
return ( qr ( nod * 2 , l , mid , x , y ) + qr ( nod * 2 + 1 , mid + 1 , r , x , y ) );
}
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;
int ffff = 0;
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;
if ( x != i + 1 || y != i + 2 ) ffff = 1;
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 ( ffff == 0 )
{
int ks = 1;
vector < pair < int , int > > vv;
for ( int i = 1 ; i <= m ; i ++ )
{
if ( s [i] < t [i] ) vv . push_back ( { s [i] , t [i] } );
up ( 1 , 0 , n , s [i] , 1 );
}
sort ( vv . begin () , vv . end () );
for ( int i = vv . size () - 1 ; i >= 0 ; i -- )
{
int x = vv [i] . first , y = vv [i] . second;
if ( qr ( 1 , 0 , n , x + 1 , y ) >= 1 ) ks = 0;
up ( 1 , 0 , n , x , -1 );
up ( 1 , 0 , n , y , 1 );
}
vv . clear ();
for ( int i = 1 ; i <= m ; i ++ )
{
if ( s [i] > t [i] ) vv . push_back ( { s [i] , t [i] } );
}
sort ( vv . begin () , vv . end () );
for ( int i = 0 ; i < vv . size () ; i ++ )
{
int x = vv [i] . first , y = vv [i] . second;
if ( qr ( 1 , 0 , n , x + 1 , y ) >= 1 ) ks = 0;
up ( 1 , 0 , n , x , -1 );
up ( 1 , 0 , n , y , 1 );
}
if ( ks == 0 ) cout << "No" << endl;
else cout << "Yes" << endl;
for ( int i = 1 ; i <= m ; i ++ ) up ( 1 , 0 , n , t [i] , -1 );
}
else
{
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
*/
Compilation message
jail.cpp: In function 'int main()':
jail.cpp:142:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for ( int i = 0 ; i < vv . size () ; i ++ )
| ~~^~~~~~~~~~~~~~
| # |
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 |
19008 KB |
Output is correct |
| 4 |
Incorrect |
37 ms |
19156 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
19104 KB |
Output is correct |
| 2 |
Correct |
13 ms |
19080 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
19156 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
19104 KB |
Output is correct |
| 2 |
Correct |
13 ms |
19080 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
19156 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
19104 KB |
Output is correct |
| 2 |
Correct |
13 ms |
19080 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
19156 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
19104 KB |
Output is correct |
| 2 |
Correct |
13 ms |
19080 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
19156 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
19028 KB |
Output is correct |
| 2 |
Correct |
11 ms |
19024 KB |
Output is correct |
| 3 |
Correct |
9 ms |
19028 KB |
Output is correct |
| 4 |
Correct |
11 ms |
19028 KB |
Output is correct |
| 5 |
Incorrect |
22 ms |
19044 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
19008 KB |
Output is correct |
| 4 |
Incorrect |
37 ms |
19156 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
