제출 #557598

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
557598		DanShaders	Jail (JOI22_jail)	C++17	100 / 100	507 ms	72716 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) {
	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;
			g[--u].push_back(--v);
			g[v].push_back(u);
		}
		timer = 0;
		dfs_sz();
		dfs_hld();
		assert(timer == n);

		cin >> m;


		for (int i = 2 * n - 1; i > 0; --i) {
			g2[i / 2].push_back(i);
			g2[2 * n + i].push_back(2 * n + i / 2);
		}

		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) {
				int x = n + l + (l == s ? 1 : 0), y = n + r - (r == s ? 1 : 0);
				while (x <= y) {
					if (x & 1)	g2[u].push_back(x);
					if (!(y & 1))	g2[u].push_back(y);
					x = (x + 1) / 2;
					y = (y - 1) / 2;
				}
				// for (int i = l; i <= r; ++i) {
				// 	if (i != s) {
				// 		g2[u].push_back(n + i);
				// 	}
				// }

				x = n + l + (l == t ? 1 : 0), y = n + r - (r == t ? 1 : 0);
				while (x <= y) {
					if (x & 1)	g2[2 * n + x].push_back(u);
					if (!(y & 1))	g2[2 * n + y].push_back(u);
					x = (x + 1) / 2;
					y = (y - 1) / 2;
				}
				// 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));
			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) {
			if (!used[i]) {
				flag &= dfs_cycle(i);
			}
		}
		cout << (flag ? "Yes\n" : "No\n");
	}
}

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