Submission #1124810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124810		vako_p	Jail (JOI22_jail)	C++20	72 / 100	5132 ms	763908 KiB

jail

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
 
const int mxN = 2e5 + 5;
ll n,m,tt,in[mxN],out[mxN],p[mxN][21],st[mxN],ed[mxN],vis[mxN];
vector<ll> v[mxN],vv[mxN],start[mxN],nds[mxN];

void dfs(ll at, ll par){
	in[at] = ++tt;
	p[at][0] = par;
	for(int i = 1; i < 20; i++) p[at][i] = p[p[at][i - 1]][i - 1];
	for(auto it : v[at]){
		if(it == par) continue;
		dfs(it, at);
 	}
 	out[at] = tt;
}

bool check(ll at, ll it){
	return (in[at] <= in[it] and out[at] >= out[it]);
}

void add(ll at, ll it){
	vv[at].pb(it);
//	cout << at << ' ' << it << "---" << '\n';
}

void add_edges(){
	for(int i = 1; i <= m; i++){
		ll at = st[i], it = ed[i];
		while(true){
			for(auto it1 : start[at]){
				if(it1 != i) add(it1, i);
			}
			for(auto it1 : nds[at]){
				if(it1 != i) add(i, it1);
			}
			if(check(at, it)) break;
			at = p[at][0];
		}
		while(!check(it, at)){
			for(auto it1 : start[it]){
				if(it1 != i) add(it1, i);
			}
			for(auto it1 : nds[it]){
				if(it1 != i) add(i, it1);
			}
			it = p[it][0];
		}
	}
}

bool dfs1(ll at){
	if(vis[at]) return true;
	vis[at] = 1;
	for(auto it : vv[at]){
		if(vis[it] == 1) return false;
		if(!vis[it]) if(!dfs1(it)) return false;
	}
	vis[at] = 2;
	return true;
}

bool cycle(){
	for(int i = 1; i <= m; i++){
		if(!dfs1(i)) return false;
	}
	return true;
}

void clear(){
	for(int i = 1; i <= m; i++){
		vv[i].clear();
		vis[i] = 0;
	}
	for(int i = 1; i <= n; i++){
		v[i].clear();
		start[i].clear();
		nds[i].clear();
	}
	tt = 0;
}

inline void solve(){
	cin >> n;
	for(int i = 0; i < n - 1; i++){
		ll a,b;
		cin >> a >> b;
		v[a].pb(b);
		v[b].pb(a);
	}
	cin >> m;
	for(int i = 1; i <= m; i++){
		cin >> st[i] >> ed[i];
		start[st[i]].pb(i);
		nds[ed[i]].pb(i);
	}
	v[0].pb(1);
	dfs(0, 0);
	add_edges();
//	for(auto it : nds[2]) cout << it << '\n'; 
//	for(int i = 1; i <= m; i++){
//		cout << i << "---> ";
//		for(auto it : vv[i]) cout << i << ' ';
//		cout << '\n';
//	}
	if(cycle()) cout << "Yes" << '\n';
	else cout << "No" << '\n';
	clear();
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll t;
	cin >> t;
	while(t--) solve();
}

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