제출 #787875

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
787875		iee	Jail (JOI22_jail)	C++17	0 / 100	39 ms	42712 KiB

jail

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 900005;
int n, m;
int st[N], to[N];
vector<int> tr[N], e[N];
int bh[N];
int ma;
int dfn[N], faz[N], dep[N], siz[N], son[N], top[N];
int dfn_now;
void dfs1(int u, int fa) {
	faz[u] = fa;
	dep[u] = dep[fa] + 1;
	siz[u] = 1;
	for (int v : tr[u]) {
		if (v == fa) {
			continue;
		}
		dfs1(v, u);
		siz[u] += siz[v];
		if (siz[v] > siz[son[u]]) {
			son[u] = v;
		}
	}
}
void dfs2(int u, int tp) {
	top[u] = tp;
	dfn[u] = ++dfn_now;
	if (son[u]) {
		dfs2(son[u], tp);
	}
	for (int v : tr[u]) {
		if (v == faz[u] || v == son[u]) {
			continue;
		}
		dfs2(v, v);
	}
}
vector<int> bb;
void cqj(int u, int l, int r, int ql, int qr) {
	if (l >= ql && r <= qr) {
		bb.push_back(u);
		return;
	}
	const int mid = (l + r) >> 1;
	if (ql <= mid) cqj(u << 1, l, mid, ql, qr);
	if (qr > mid) cqj(u << 1 | 1, mid + 1, r, ql, qr);
}
void jqj(int di, int L, int R) {
	cqj(1, 1, n, L, R);
	e[di].insert(e[di].end(), bb.begin(), bb.end());
	bb.clear();
}
void jia(int di, int L, int R, int zho) {
	if (R < zho || L > zho) {
		jqj(di, L, R);
	} else {
		if (L < zho) jqj(di, L, zho - 1);
		if (zho < R) jqj(di, zho + 1, R);
	}
}
void jb(int di, int u, int v) {
	int zho = v;
	while (top[u] != top[v]) {
		if (dep[top[u]] < dep[top[v]]) {
			swap(u, v);
		}
		jia(di, dfn[top[u]], dfn[u], zho);
		u = faz[top[u]];
	}
	if (dep[u] < dep[v]) {
		swap(u, v);
	}
	jia(di, dfn[v], dfn[u], zho);
}
void xj(int u, int l, int r) {
	if (u != 1) {
		e[u / 2].push_back(u);
	}
	if (l == r) {
		bh[l] = u;
		return;
	}
	const int mid = (l + r) >> 1;
	xj(u << 1, l, mid);
	xj(u << 1 | 1, mid + 1, r);
}
bool vis[N], ins[N];
bool dag() {
	bool flag = 1;
	function<void(int)> dfs = [&](int u) {
		if (ins[u]) {
			flag = 0;
			return;
		}
		if (vis[u]) {
			return;
		}
		ins[u] = 1;
		vis[u] = 1;
		for (int v : e[u]) {
			dfs(v);
			if (!flag) {
				break;
			}
		}
		ins[u] = 0;
	};
	for (int i = 1; i <= ma + m; i++) {
		dfs(i);
	}
	return flag;
}
void solve() {
	cin >> n;
	for (int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		tr[u].push_back(v);
		tr[v].push_back(u);
	}
	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> st[i] >> to[i];
	}
	dfs1(1, 0), dfs2(1, 1);
	ma = n * 4 + 10;
	xj(1, 1, n);
	for (int u = 1; u <= m; u++) {
		jb(u + ma, st[u], to[u]);
	}
	for (int v = 1; v <= m; v++) {
		e[bh[dfn[to[v]]]].push_back(v + ma);
	}
	if (dag()) cout << "Yes" << "\n";
	else cout << "No" << "\n";
}
void clear() {
	for (int i = 1; i <= ma + m; i++) {
		st[i] = to[i] = bh[i] = dfn[i] = faz[i] = dep[i] = siz[i] = son[i] = top[i] = vis[i] = ins[i] = 0;
		tr[i].clear(), e[i].clear();
	}
	n = m = ma = dfn_now = 0;
}
int main() {
	int T;
	cin >> T;
	while (T--) {
		solve();
		clear();
	}
	return 0;
}

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