Submission #891123

#	Time	Username	Problem	Language	Result	Execution time	Memory
891123		vjudge1	Jail (JOI22_jail)	C++17	21 / 100	51 ms	7516 KiB

jail

#include <bits/stdc++.h>
using namespace std;/*
<<<<It's never too late for a new beginning in your life>>>>
Today is hard
  tomorrow will worse
  but the day after tomorrow will be the sunshine..
 
HARD WORK BEATS TALENT WHEN TALENT DOESN'T WORK HARD............
Never give up  */
//The most CHALISHKANCHIK
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
//~ #define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vii;
const long long N = 1e5+50, inf = 1e18, mod = 1e9+7;
  vector<int>v[N],pred(N);
  vector<int>col(N),vis(N);
void dfs(int x,int pr){
	vis[x] = 1;
	for(auto to:v[x]){
		if(to==pr||col[to])continue;
		dfs(to,x);
	}
}
void solve(){
	int n,m;
	cin>>n;
	for(int i = 1;i<=n;i++){
		v[i].clear();
		vis[i] = 0;
		col[i] = 0;
	}
	for(int i = 1;i<n;i++){
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
	}
	cin>>m;
	vector<pii>g(m);
	for(int i = 0;i<m;i++){
		int a,b;
		cin>>a>>b;
		g[i] = {a, b};
	}
  	if(m<=6){
   	vector<int>ind;
   	for(int i = 0;i<m;i++)ind.pb(i);

   	do
   	{
		for(int i = 1;i<=n;i++)col[i] = 0;
		for(auto to:g){
			col[to.ff] += 1;
		}
		bool flag = true;
    	for(auto to:ind){
     		int a = g[to].ff;
     		int b = g[to].ss;
     		col[a]--;
     		for(int i = 1;i<=n;i++)vis[i] = 0;
		 		if(col[a]>=1){
		  			flag = false;
		  			break;
		 		}
				dfs(a,-1);
				col[b] ++;
				if(vis[b]==0){
					flag = false;
					break;
				}
			}
			if(flag){
				cout<<"Yes\n";
				return;
			}
		}while (next_permutation(all(ind)));
		
		cout<<"No\n";
  	}
  	else{
		sort(all(g));
		int mn = 1e9;
		for(int i = m-1;i>=0;i--){
			if(mn < g[i].ss){
				cout<<"No\n";
				return;
			}
			mn = min(mn, g[i].ss);
		}
		cout << "Yes\n";
  }
}
main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int t = 1;
	cin >> t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

jail.cpp:101:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  101 | main(){
      | ^~~~

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23