제출 #788211

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

jail

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1000;
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> path[N][N];
void jb(int di, int u, int v) {
	auto pa = path[u][v];
	pa.pop_back();
	for (int x : pa) {
		e[di].push_back(x);
	}
}
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);
	}
	for (int S = 1; S <= n; S++) {
		queue<int> Q;
		Q.push(S);
		vector<int> vis(n + 1);
		vis[S] = 1;
		path[S][S] = {S};
		while (!Q.empty()) {
			int u = Q.front();
			Q.pop();
			for (int v : tr[u]) {
				if (!vis[v]) {
					vis[v] = 1;
					path[S][v] = path[S][u];
					path[S][v].push_back(v);
					Q.push(v);
				}
			}
		}
	}
	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> st[i] >> to[i];
	}
	dfs1(1, 0), dfs2(1, 1);
	ma = n;
	for (int u = 1; u <= m; u++) {
		jb(u + ma, st[u], to[u]);
	}
	for (int v = 1; v <= m; v++) {
		e[to[v]].push_back(v + ma);
	}
	if (dag()) cout << "Yes" << "\n";
	else cout << "No" << "\n";
}
void clear() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			path[i][j].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