Submission #935992

#	Time	Username	Problem	Language	Result	Execution time	Memory
935992		TAhmed33	Jail (JOI22_jail)	C++98	49 / 100	5073 ms	1048576 KiB

jail

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 120025;
int n, m;
pair <int, int> a[MAXN];
vector <int> adj[MAXN];
set <int> path[MAXN];
vector <int> comp;
bool flag;
void dfs (int pos, int par, int c) {
	comp.push_back(pos);
	if (pos == a[c].second) {
		flag = 1;
		return;
	}
	for (auto j : adj[pos]) {
		if (j == par) continue;
		dfs(j, pos, c);
		if (flag) return;
	}
	comp.pop_back();
}
int vis[MAXN];
void dfs2 (int pos) {
	vis[pos] = 1;
	comp.push_back(pos);
	for (int i = 1; i <= m; i++) {
		if (i == pos) continue;
		if (path[pos].count(a[i].first)) {
			if (vis[i] == 1) {
				flag = 1;
				return;
			}
			if (vis[i] == 0) {
				dfs2(i);
				if (flag) return;
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		if (i == pos) continue;
		if (path[i].count(a[pos].second)) {
			if (vis[i] == 1) {
				flag = 1;
				return;
			}
			if (vis[i] == 0) {
				dfs2(i);
				if (flag) return;
			}
		}
	}
	if (flag) return;
	vis[pos] = 2;
	comp.pop_back();
}
void solve () {
	cin >> n;
	for (int i = 1; i <= n; i++) adj[i].clear();
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> a[i].first >> a[i].second; vis[i] = 0;
		path[i].clear(); comp.clear(); flag = 0;
		dfs(a[i].first, -1, i);
		for (auto j : comp) path[i].insert(j);
	}
	flag = 0;
	comp.clear();
	for (int i = 1; i <= n && !flag; i++) {
		if (vis[i] == 0) {
			comp.clear();
			dfs2(i);
		}
	}
	cout << (flag ? "No\n" : "Yes\n");
}
int main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int t = 1; cin >> t;
	while (t--) solve();
}

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