Submission #600514

#	Time	Username	Problem	Language	Result	Execution time	Memory
600514		Bobaa	Jail (JOI22_jail)	C++17	100 / 100	605 ms	64648 KiB

jail

#include <bits/stdc++.h>
using namespace std; 

const int maxn = 120005; 

vector<int> g[maxn]; 
int n, par[maxn], hd[maxn], sz[maxn], dep[maxn], dfn[maxn], seq[maxn], best[maxn], dft, memtp, tg[10 * maxn], tp, indeg[10 * maxn]; 
pair<int, int> walk[maxn], mem[100 * maxn]; 

struct node {
	int up, dwn; 
} seg[maxn << 2]; 

void adde(int u, int v) {
	mem[++memtp] = pair<int, int>(tg[u], v); 
	tg[u] = memtp; 
	++indeg[v]; 
}

void build(int l, int r, int rt) {
	if (l == r) {
		seg[rt].up = l; 
		seg[rt].dwn = l + n; 
		return; 
	}
	seg[rt].up = ++tp; 
	indeg[tp] = 0; 
	tg[tp] = 0; 
	seg[rt].dwn = ++tp; 
	indeg[tp] = 0; 
	tg[tp] = 0; 
	int mid = (l + r) >> 1; 
	build(l, mid, rt << 1); 
	build(mid + 1, r, rt << 1 | 1); 
	adde(seg[rt << 1].up, seg[rt].up); 
	adde(seg[rt << 1 | 1].up, seg[rt].up); 
	adde(seg[rt].dwn, seg[rt << 1].dwn); 
	adde(seg[rt].dwn, seg[rt << 1 | 1].dwn); 
}

void modify(int L, int R, int l, int r, int rt, int up, int idx) {
	if (L <= l && R >= r) {
		if (up) adde(seg[rt].up, idx); 
		else adde(idx, seg[rt].dwn); 
		return; 
	}
	int mid = (l + r) >> 1; 
	if (L <= mid) modify(L, R, l, mid, rt << 1, up, idx); 
	if (R > mid) modify(L, R, mid + 1, r, rt << 1 | 1, up, idx); 
}

void dfs1(int u, int f) {
	par[u] = f; 
	sz[u] = 1; 
	best[u] = 0; 
	for (auto v : g[u]) if (v != f) {
		dep[v] = dep[u] + 1; 
		dfs1(v, u); 
		sz[u] += sz[v]; 
		if (sz[best[u]] < sz[v]) best[u] = v; 
	}
}

void dfs2(int u, int h) {
	hd[u] = h; 
	dfn[u] = ++dft; 
	seq[dft] = u; 
	if (best[u]) dfs2(best[u], h); 
	for (auto v : g[u]) if (v != par[u] && v != best[u]) dfs2(v, v); 
}

void pathadd(int u, int v, int up, int idx) {
	int ban = v; 
	while (hd[u] != hd[v]) {
		if (dep[hd[u]] < dep[hd[v]]) swap(u, v); 
		if (u != ban) modify(dfn[hd[u]], dfn[u], 1, n, 1, up, idx); 
		else if (dfn[hd[u]] < dfn[u]) modify(dfn[hd[u]], dfn[u] - 1, 1, n, 1, up, idx); 
		u = par[hd[u]]; 
	}
	if (dfn[u] > dfn[v]) swap(u, v); 
	if (u != ban && v != ban) modify(dfn[u], dfn[v], 1, n, 1, up, idx); 
	else if (u == ban && dfn[u] < dfn[v]) modify(dfn[u] + 1, dfn[v], 1, n, 1, up, idx); 
	else if (v == ban && dfn[u] < dfn[v]) modify(dfn[u], dfn[v] - 1, 1, n, 1, up, idx); 
}

bool solve() {
	memtp = 0; 
	int m; 
	cin >> n; 
	tp = n * 2; 
	for (int i = 1; i <= n; i++) {
		g[i].clear(); 
		indeg[i] = tg[i] = indeg[i + n] = tg[i + n] = 0;
	}
	build(1, n, 1); 
	for (int i = 1, a, b; i < n; i++) {
		cin >> a >> b; 
		g[a].push_back(b); 
		g[b].push_back(a); 
	}
	dft = 0; 
	dfs1(1, 1); 
	dfs2(1, 1); 
	cin >> m; 
	for (int i = 1; i <= m; i++) {
		indeg[tp + i] = tg[tp + i] = 0; 
		cin >> walk[i].first >> walk[i].second;
	}
	for (int i = 1; i <= m; i++) {
		adde(tp + i, dfn[walk[i].first]); 
		adde(dfn[walk[i].second] + n, tp + i); 
	}
	for (int i = 1; i <= m; i++) {
		int u = walk[i].first, v = walk[i].second; 
		pathadd(u, v, 0, tp + i); 
		pathadd(v, u, 1, tp + i); 
	}
	tp += m; 
	queue<int> q; 
	for (int i = 1; i <= tp; i++) if (!indeg[i]) q.push(i); 
	while (!q.empty()) {
		int u = q.front(); 
		q.pop(); 
		while (tg[u] != 0) {
			if (!--indeg[mem[tg[u]].second]) q.push(mem[tg[u]].second); 
			tg[u] = mem[tg[u]].first; 
		}
	}
	for (int i = 1; i <= tp; i++) if (indeg[i]) return 0; 
	return 1; 
}

int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(nullptr); 
	int t; 
	cin >> t; 
	while (t--) {
		if (solve()) cout << "Yes" << '\n'; 
		else cout << "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