Submission #557597

#	Time	Username	Problem	Language	Result	Execution time	Memory
557597		DanShaders	Jail (JOI22_jail)	C++17	72 / 100	2451 ms	1048576 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;

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

char used[M];

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;
}

int sz[N];

int dfs_sz(int u = 0, int p = -1) {
	int res = 1;
	for (int v : g[u]) {
		if (v != p) {
			res += dfs_sz(v, u);
		}
	}
	return sz[u] = res;
}

int timer, order[N], lnk[N], tout[N], parent[N];

void dfs_hld(int u = 0, int up = 0, int p = -1) {
	// cout << u << " " << up << " " << p << endl;
	order[u] = timer;
	parent[timer] = p == -1 ? -1 : order[p];
	lnk[timer] = order[up];
	++timer;
	sort(all(g[u]), [](int x, int y) {
		return sz[x] > sz[y];
	});
	bool is_first = true;
	for (int v : g[u]) {
		if (v != p) {
			dfs_hld(v, is_first ? up : v, u);
			is_first = false;
		}
	}
	tout[order[u]] = timer;
}

bool in(int x0, int y0, int x1, int y1) {
	return x0 <= x1 && y1 <= y0;
}

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;
			// cout << u << " " << v << endl;
			g[--u].push_back(--v);
			g[v].push_back(u);
		}
		timer = 0;
		dfs_sz();
		dfs_hld();
		// cout << timer << endl;
		assert(timer == n);

		cin >> m;
		for (int person = 0; person < m; ++person) {
			int u = 4 * n + person;

			int s, t;
			cin >> s >> t;
			s = order[s - 1], t = order[t - 1];

			auto use_cut = [&](int l, int r) {
				// cout << l << " " << r << endl;
				for (int i = l; i <= r; ++i) {
					if (i != s) {
						g2[u].push_back(n + i);
					}
				}
				for (int i = l; i <= r; ++i) {
					if (i != t) {
						g2[3 * n + i].push_back(u);
					}
				}
			};

			int a = s, b = t;
			while (lnk[a] != lnk[b]) {
				if (!in(lnk[a], tout[lnk[a]], b, tout[b])) {
					use_cut(lnk[a], a);
					a = parent[lnk[a]];
				} else {
					assert(!in(lnk[b], tout[lnk[b]], a, tout[a]));
					use_cut(lnk[b], b);
					b = parent[lnk[b]];
				}
			}
			use_cut(min(a, b), max(a, b));
			// 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].push_back(u);
			g2[u].push_back(3 * n + t);
		}
		fill(used, used + 5 * n, 0);
		bool flag = true;
		for (int i = 0; i < 5 * n; ++i) {
			// for (int j : g2[i]) {
			// 	cout << i << " -> " << j << endl;
			// }
			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: 11 / 11
• Subtask 7: 0 / 23