oj.uz

Submission #788211

# Submission time Handle Problem Language Result Execution time Memory
788211 2023-07-20T01:26:13 Z iee Jail (JOI22_jail) C++17
0 / 100
 192 ms 65364 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 14 ms 23764 KB Output is correct
3 Correct 12 ms 23840 KB Output is correct
4 Incorrect 192 ms 28804 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23828 KB Output is correct
3 Incorrect 137 ms 65364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23828 KB Output is correct
3 Incorrect 137 ms 65364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23828 KB Output is correct
3 Incorrect 137 ms 65364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23828 KB Output is correct
3 Incorrect 137 ms 65364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23844 KB Output is correct
2 Correct 11 ms 23832 KB Output is correct
3 Correct 12 ms 23832 KB Output is correct
4 Correct 12 ms 23844 KB Output is correct
5 Incorrect 30 ms 24052 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 14 ms 23764 KB Output is correct
3 Correct 12 ms 23840 KB Output is correct
4 Incorrect 192 ms 28804 KB Output isn't correct
5 Halted 0 ms 0 KB -