oj.uz

Submission #891089

# Submission time Handle Problem Language Result Execution time Memory
891089 2023-12-22T07:28:27 Z vjudge1 Jail (JOI22_jail) C++17
5 / 100
 21 ms 97116 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

bool YES(bool f){ if(f) cout << "Yes\n" ; else cout << "No\n" ; return f ; }
void YES(){YES(1);}
void NO(){YES(0);}
void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
//#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ios ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);
#define int long long
#define ld long double
#define pii pair <int , int>
#define ff first
#define ss second
#define endl '\n'

const int N = 2e6 + 5 ;
const int inf = 1e18 ;
const int mod = 998244353 ;
const double eps = 1e-8 ;

int binpow( int a , int b ){
  if ( b == 0 ) return 1 ;
  int x = binpow ( a , b/2 ) ;
  if ( !(b%2) ) return (x*x) ;
  return (x*x*a) ;
}
template <class T>
bool chmax( T& x , const T& y ){
  bool f = 0 ;
  if ( x < y ) x = y , f = 1 ;
  return f ;
}
template <class T>
bool chmin( T &x , const T &y ){
  bool f = 0 ;
  if ( x > y ) x = y , f = 1 ;
  return f ;
}

//code

int n , m , ans , p ;
bool f ;
int a[N] , b[N] ;
vector <int> g[N] , vis[N] ;
pii c[N] ;

bool dfs ( int v , int p , int x , int i ){
	if ( v == x ){
		vis[x].push_back(i) ;
		return 1 ;
	}
	for ( auto to : g[v] ) if ( to != p && dfs ( to , v , x , i ) ){ vis[v].push_back(i) ; return 1 ;}
	return 0 ;
}

void solve(){
	f = 0 ;
	cin >> n ;
	for ( int i = 1 ; i <= n ; i ++ ) g[i].clear() , vis[i].clear() ;
	for ( int i = 1 ; i < n ; i ++ ){
		int x , y ; cin >> x >> y ;
		f &= ( x == i && y == x+1 ) ;
		g[x].push_back(y) ;
		g[y].push_back(x) ;
	}
	cin >> m ;
	for ( int i = 0 ; i < m ; i ++ ) cin >> a[i] >> b[i] ;
	if (f){
		for ( int i = 0 ; i < m ; i ++ ) c[i].ff = a[i] , c[i].ss = b[i] ;
		sort ( c , c + m ) ;
		set <int> st ;
		for ( int i = 0 ; i < m ; i ++ ) st.insert(b[i]) ;
		for ( int i = 0 ; i < m ; i ++ ){
			st.erase(c[i].ss) ;
			if ( c[i].ss < c[i].ff ) continue ;
			if ( st.upper_bound(min(c[i].ff,c[i].ss)) != st.end() && *st.upper_bound(min(c[i].ff,c[i].ss)) < max ( c[i].ff , c[i].ss ) ){
				NO() ;
				return ;
			}
		}
		YES() ;
	}
	for ( int i = 0 ; i < m ; i ++ ){
		dfs ( a[i] , 0 , b[i] , i ) ;
	}
	if ( vis[b[0]].size() > 1 && vis[b[1]].size() > 1 ) NO() ;
	else if ( vis[a[0]].size() > 1 && vis[a[1]].size() > 1 ) NO() ;
	else if ( ( vis[a[0]].size() == 2 && vis[b[0]].size() == 2 ) || ( vis[a[1]].size() == 2 && vis[b[1]].size() == 2 ) ) NO() ;
	else YES() ;
}

signed main(){
    ios ;
	int t = 1 ;
	cin >> t ;
	while ( t -- ) solve() ;
}

Compilation message

jail.cpp: In function 'void fopn(std::string)':
jail.cpp:10:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jail.cpp:10:72: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 96860 KB Output is correct
2 Incorrect 21 ms 96860 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 96856 KB Output is correct
2 Correct 20 ms 96860 KB Output is correct
3 Correct 21 ms 96860 KB Output is correct
4 Correct 21 ms 96824 KB Output is correct
5 Correct 21 ms 96860 KB Output is correct
6 Correct 21 ms 96860 KB Output is correct
7 Correct 21 ms 96856 KB Output is correct
8 Correct 21 ms 96856 KB Output is correct
9 Correct 21 ms 96860 KB Output is correct
10 Correct 21 ms 96860 KB Output is correct
11 Correct 21 ms 96820 KB Output is correct
12 Correct 21 ms 96920 KB Output is correct
13 Correct 21 ms 96856 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 96856 KB Output is correct
2 Correct 20 ms 96860 KB Output is correct
3 Correct 21 ms 96860 KB Output is correct
4 Correct 21 ms 96824 KB Output is correct
5 Correct 21 ms 96860 KB Output is correct
6 Correct 21 ms 96860 KB Output is correct
7 Correct 21 ms 96856 KB Output is correct
8 Correct 21 ms 96856 KB Output is correct
9 Correct 21 ms 96860 KB Output is correct
10 Correct 21 ms 96860 KB Output is correct
11 Correct 21 ms 96820 KB Output is correct
12 Correct 21 ms 96920 KB Output is correct
13 Correct 21 ms 96856 KB Output is correct
14 Correct 21 ms 96860 KB Output is correct
15 Incorrect 20 ms 96856 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 96856 KB Output is correct
2 Correct 20 ms 96860 KB Output is correct
3 Correct 21 ms 96860 KB Output is correct
4 Correct 21 ms 96824 KB Output is correct
5 Correct 21 ms 96860 KB Output is correct
6 Correct 21 ms 96860 KB Output is correct
7 Correct 21 ms 96856 KB Output is correct
8 Correct 21 ms 96856 KB Output is correct
9 Correct 21 ms 96860 KB Output is correct
10 Correct 21 ms 96860 KB Output is correct
11 Correct 21 ms 96820 KB Output is correct
12 Correct 21 ms 96920 KB Output is correct
13 Correct 21 ms 96856 KB Output is correct
14 Correct 21 ms 96860 KB Output is correct
15 Incorrect 20 ms 96856 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 96856 KB Output is correct
2 Correct 20 ms 96860 KB Output is correct
3 Correct 21 ms 96860 KB Output is correct
4 Correct 21 ms 96824 KB Output is correct
5 Correct 21 ms 96860 KB Output is correct
6 Correct 21 ms 96860 KB Output is correct
7 Correct 21 ms 96856 KB Output is correct
8 Correct 21 ms 96856 KB Output is correct
9 Correct 21 ms 96860 KB Output is correct
10 Correct 21 ms 96860 KB Output is correct
11 Correct 21 ms 96820 KB Output is correct
12 Correct 21 ms 96920 KB Output is correct
13 Correct 21 ms 96856 KB Output is correct
14 Correct 21 ms 96860 KB Output is correct
15 Incorrect 20 ms 96856 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 96860 KB Output is correct
2 Correct 21 ms 96860 KB Output is correct
3 Incorrect 21 ms 97116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 96860 KB Output is correct
2 Incorrect 21 ms 96860 KB Output isn't correct
3 Halted 0 ms 0 KB -