Submission #557589

#	Time	Username	Problem	Language	Result	Execution time	Memory
557589		DanShaders	Jail (JOI22_jail)	C++17	49 / 100	5096 ms	506716 KiB

jail

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

namespace x = __gnu_pbds;
template <typename T>
using ordered_set = x::tree<T, x::null_type, less<T>, x::rb_tree_tag, x::tree_order_statistics_node_update>;

template <typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
#define x first
#define y second
using ll = long long;
using ld = long double;

const int N = 1.25e5, M = 5 * N;

int s[N], t[N];
vector<int> g[N], g2[M];

char used[N];
vector<int> path;

bool dfs_cycle(int u) {
	if (used[u] == 1) {
		return false;
	}
	used[u] = 1;
	for (int v : g2[u]) {
		if (used[v] != 2 && !dfs_cycle(v)) {
			return false;
		}
	}
	used[u] = 2;
	return true;
}

bool dfs(int u, int w, int p = -1) {
	path.push_back(u);
	if (u == w) {
		return true;
	}
	for (int v : g[u]) {
		if (v != p && dfs(v, w, u)) {
			return true;
		}
	}
	path.pop_back();
	return false;
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	int testcases;
	cin >> testcases;
	while (testcases--) {
		int n, m;
		cin >> n;
		for (int i = 0; i < 5 * n; ++i) {
			g2[i].clear();
		}
		for (int i = 0; i < n; ++i) {
			g[i].clear();
		}
		for (int i = 1; i < n; ++i) {
			int u, v;
			cin >> u >> v;
			g[--u].push_back(--v);
			g[v].push_back(u);
		}
		cin >> m;
		for (int i = 0; i < m; ++i) {
			cin >> s[i] >> t[i];
			--s[i], --t[i];
			
			path.clear();
			dfs(s[i], t[i]);

			for (int u : path) {
				if (u != s[i]) {
					g2[4 * n + i].push_back(n + u);
				}
			}
			for (int u : path) {
				if (u != t[i]) {
					g2[3 * n + u].push_back(4 * n + i);
				}
			}
			g2[n + s[i]].push_back(4 * n + i);
			g2[4 * n + i].push_back(3 * n + t[i]);
		}
		// for (int i = 0; i < 5 * n; ++i) {
		// 	for (int v : g[i]) {
		// 		cout << i << " -> " << v << endl;
		// 	}
		// }
		fill(used, used + 5 * n, 0);
		bool flag = true;
		for (int i = 0; i < 5 * n; ++i) {
			if (!used[i]) {
				flag &= dfs_cycle(i);
			}
		}
		cout << (flag ? "Yes\n" : "No\n");
	}
}

• 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