Submission #557582

#	Time	Username	Problem	Language	Result	Execution time	Memory
557582		DanShaders	Jail (JOI22_jail)	C++17	61 / 100	5088 ms	265632 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.3e5;

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

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 < n; ++i) {
			g[i].clear();
			g2[i].clear();
			paths[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) {
				paths[u].push_back(i);
			}
		}
		for (int i = 0; i < m; ++i) {
			for (int j : paths[s[i]]) {
				if (i != j) {
				// cout << j << " -> "  << i << endl;
					g2[j].push_back(i);
				}
			}
			for (int j : paths[t[i]]) {
				// cout << i << " -> "  << j << endl;
				if (i != j) {
					g2[i].push_back(j);
				}
			}
		}
		fill(used, used + m, 0);
		bool flag = true;
		for (int i = 0; i < m; ++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: 12 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23