Submission #545182

#	Time	Username	Problem	Language	Result	Execution time	Memory
545182		inksamurai	Jail (JOI22_jail)	C++17	0 / 100	0 ms	212 KiB

jail

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3x2WzQf ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e

void slv(){
	int n;
	cin>>n;
	vec(vi) adj(n);
	rep(i,n-1){
		int u,v;
		cin>>u>>v;
		u-=1,v-=1;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	int m;
	cin>>m;
	vi to(n,-1),ids(n,-1),idt(n,-1);
	rep(i,m){
		int s,t;
		cin>>s>>t;
		s-=1,t-=1;
		ids[s]=i;
		idt[t]=i;
		to[s]=t;
	}

	int s;
	vec(vi) gr(m);
	auto walk=[&](auto self,int v,int par,int t)->bool{
		bool type=0;
		for(auto u:adj[v]){
			if(u==par) continue;
			type=type or self(self,u,v,t);
		}
		type=type or v==t;
		if(type){
			if(s!=v and ids[v]!=-1){
				gr[ids[v]].pb(ids[s]);
			}
			if(s!=v and idt[v]!=-1){
				gr[ids[s]].pb(idt[v]);
			}
		}
		return type;
	};


	rep(v,n){
		if(ids[v]!=-1){
			s=v;
			walk(walk,v,-1,to[v]);
		}
	}

	vi usd(m,0),usd1(m,0);
	bool cyc=0;
	auto dfs=[&](auto self,int v)->void{
		usd[v]=1;
		usd1[v]=1;
		for(auto u:gr[v]){
			if(usd1[u]){
				cyc=1;
			}
			if(!usd[u]){
				self(self,u);
			}
		}
		usd1[v]=0;
	};

	// rep(v,m){
	// 	print(v);
	// 	for(auto u:gr[v]){
	// 		cout<<u<<" ";
	// 	}
	// 	cout<<"\n";
	// }

	rep(v,m){
		if(!usd[v]){
			dfs(dfs,0);
		}
	}
	cout<<(cyc?"No":"Yes")<<"\n";
}

signed main(){
_3x2WzQf;
	int t;
	cin>>t;
	rep(cs,t){
		slv();
	}
//	
	return 0;
}

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