Submission #547411

#	Time	Username	Problem	Language	Result	Execution time	Memory
547411		skittles1412	Jail (JOI22_jail)	C++17	100 / 100	719 ms	77868 KiB

jail

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

const int maxn = 1 << 17, logn = 17;

int n, t, arr[maxn][2], tin[maxn], tout[maxn], tord[maxn], chain[maxn], siz[maxn], lift[logn][maxn],
	ntost[maxn], leaf[maxn * 2], startv[maxn];
vector<int> graph[maxn], st[maxn * 2];

void dfs(int u) {
	siz[u] = 1;
	for (auto& v : graph[u]) {
		graph[v].erase(find(begin(graph[v]), end(graph[v]), u));
		lift[0][v] = u;
		dfs(v);
		siz[u] += siz[v];
		if (siz[v] > siz[graph[u][0]]) {
			swap(v, graph[u][0]);
		}
	}
}

void hdfs(int u) {
	tin[u] = t++;
	for (auto& v : graph[u]) {
		if (v == graph[u][0]) {
			chain[v] = chain[u];
		} else {
			chain[v] = v;
		}
		hdfs(v);
	}
	tout[u] = t - 1;
}

bool anc(int u, int v) {
	return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca(int u, int v) {
	if (anc(u, v)) {
		return u;
	}
	for (int i = logn - 1; i >= 0; i--) {
		int nu = lift[i][u];
		if (nu != -1 && !anc(nu, v)) {
			u = nu;
		}
	}
	return lift[0][u];
}

template <typename T>
void hld(int u, int v, bool incl, bool incr, const T& t) {
	assert(anc(u, v));
	if (!incr) {
		v = lift[0][v];
	}
	while (v != -1 && anc(u, v)) {
		int cl = max(tin[u] + (!incl), tin[chain[v]]);
		if (cl <= tin[v]) {
			t(cl, tin[v]);
		}
		v = lift[0][chain[v]];
	}
}

template <typename T>
void hldp(int u, int v, bool inclu, bool inclv, const T& t) {
	if (anc(v, u)) {
		hld(v, u, inclv, inclu, t);
	} else if (anc(u, v)) {
		hld(u, v, inclu, inclv, t);
	} else {
		int l = lca(u, v);
		hld(l, u, true, inclu, t);
		hld(l, v, true, inclv, t);
	}
}

void build(int o, int l, int r) {
	if (l == r) {
		leaf[o] = l;
		ntost[l] = o;
	} else {
		int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
		build(lc, l, mid);
		build(rc, mid + 1, r);
	}
}

template <typename T>
void update(int o, int l, int r, int ql, int qr, const T& t) {
	if (ql <= l && r <= qr) {
		t(o, l, r);
	} else {
		int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
		if (ql <= mid) {
			update(lc, l, mid, ql, qr, t);
		}
		if (mid < qr) {
			update(rc, mid + 1, r, ql, qr, t);
		}
	}
}

template <typename T>
void update(int l, int r, const T& t) {
	update(1, 0, n - 1, l, r, t);
}

enum NodeType { PRISONER, ST1, ST2 };

bool found;
int vis[3][1 << 21];

void xdfs(NodeType type, int u) {
	if (found) {
		return;
	}
	dbg("I", type, u);
	if (vis[type][u]) {
		if (vis[type][u] == 1) {
			found = true;
		}
		return;
	}
	vis[type][u] = 1;
	if (type == PRISONER) {
		xdfs(ST1, ntost[tin[arr[u][1]]]);
		dbg(arr[u][0], arr[u][1], u);
		hldp(arr[u][0], arr[u][1], false, true, [&](int l, int r) -> void {
			dbg(l, r);
			update(l, r, [&](int o, int, int) -> void {
				xdfs(ST2, o);
			});
		});
	} else if (type == ST1) {
		for (auto& a : st[u]) {
			xdfs(PRISONER, a);
		}
		if (u > 1) {
			xdfs(ST1, u >> 1);
		}
	} else {
		if (leaf[u] != -1) {
			int v = startv[tord[leaf[u]]];
			if (v != -1) {
				xdfs(PRISONER, v);
			}
		} else {
			xdfs(ST2, u * 2);
			xdfs(ST2, u * 2 + 1);
		}
	}
	vis[type][u] = 2;
	dbg("O", type, u);
}

void solve() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		graph[i].clear();
	}
	for (int i = 0; i < min(2 * maxn, 4 * n); i++) {
		st[i].clear();
	}
	for (auto& a : vis) {
		fill(a, a + 4 * n, 0);
	}
	fill(startv, startv + n, -1);
	fill(leaf, leaf + min(2 * maxn, 4 * n), -1);
	t = 0;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	lift[0][0] = -1;
	dfs(0);
	hdfs(0);
	for (int i = 0; i < n; i++) {
		tord[tin[i]] = i;
	}
	for (int i = 1; i < logn; i++) {
		for (int j = 0; j < n; j++) {
			if (lift[i - 1][j] == -1) {
				lift[i][j] = -1;
			} else {
				lift[i][j] = lift[i - 1][lift[i - 1][j]];
			}
		}
	}
	int m;
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> arr[i][0] >> arr[i][1];
		arr[i][0]--;
		arr[i][1]--;
	}
	for (int i = 0; i < m; i++) {
		auto& [a, b] = arr[i];
		startv[a] = i;
		hldp(a, b, true, false, [&](int l, int r) -> void {
			dbg(l, r);
			update(l, r, [&](int o, int, int) -> void {
				st[o].push_back(i);
			});
		});
	}
	build(1, 0, n - 1);
	found = false;
	for (int i = 0; i < m; i++) {
		dbg(i);
		xdfs(PRISONER, i);
	}
	if (found) {
		cout << "No" << endl;
	} else {
		cout << "Yes" << endl;
	};
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	int tcs;
	cin >> tcs;
	while (tcs--) {
		solve();
	}
}

• 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