oj.uz

Submission #1015394

# Submission time Handle Problem Language Result Execution time Memory
1015394 2024-07-06T10:05:39 Z vjudge3 Jail (JOI22_jail) C++17
0 / 100
 20 ms 61276 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> g[120005];
vector<pair<int, int>> h[120005][20];
int lift[120005][20], d[120005], tin[120005], tout[120005], timer, lg, col[120005][20];
bool hv[120005], ans = true;

void dfs(int u, int p) {
	tin[u] = ++timer;
	lift[u][0] = p;
	for (int i = 1; i <= lg; i++) lift[u][i] = lift[lift[u][i-1]][i-1];
	for (auto& v : g[u]) if (v != p) {
		d[v] = d[u]+1;
		dfs(v, u);
	}
	tout[u] = timer;
}

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

int lca(int s, int t) {
	if (anc(s, t)) return s;
	for (int i = lg; i >= 0; i--) if (!anc(lift[s][i], t)) s = lift[s][i];
	return lift[s][0];
}

void dfs_cyc(int u, int k) {
	col[u][k] = 1;
	for (auto& [v, l] : h[u][k]) if (col[v][l] != 2) {
		if (col[v][l] == 1) ans = false;
		else dfs_cyc(v, l);
	}
	col[u][k] = 2;
}

void solve() {
	int n, m;
	cin >> n;
	lg = __lg(n);
	timer = 0;
	ans = 1;
	for (int i = 1; i <= n; i++) {
		g[i].clear();
		d[i] = tin[i] = tout[i] = hv[i] = 0;
		for (int j = 0; j <= lg; j++) {
			h[i][j].clear();
			lift[i][j] = col[i][j] = 0;
		}
	}
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	cin >> m;
	vector<pair<int, int>> path (m);
	bool ok = true;
	for (auto& [s, t] : path) {
		cin >> s >> t;
		if (hv[t]) ok = false;
		hv[t] = true;
	}
	if (!ok) {
		cout << "No\n";
		return;
	}
	dfs(1, 0);
	for (auto& [u, v] : path) {
		int node = v;
		int t = lca(u, v);
		if (u != t) {
			int diff = d[u] - d[t], l = __lg(diff);
			h[u][l].push_back({node, 0});
			diff -= 1<<l;
			for (int i = 0; i <= lg; i++) if (diff & (1<<i)) u = lift[u][i];
			h[u][l].push_back({node, 0});
		}
		if (v != t && (v = lift[v][0]) != t) {
			int diff = d[v] - d[t], l = __lg(diff);
			h[v][l].push_back({node, 0});
			diff -= 1<<l;
			for (int i = 0; i <= lg; i++) if (diff & (1<<i)) v = lift[v][i];
			h[v][l].push_back({node, 0});
		}
	}
	for (int i = 1; i <= n; i++) for (int j = 1; j <= lg; j++) {
		h[i][j-1].push_back({i, j});
		h[lift[i][j-1]][j-1].push_back({i, j});
	}
	for (int i = 1; i <= n; i++) if (!col[i][0]) dfs_cyc(i, 0);
	cout << (ans ? "Yes\n" : "No\n");
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int q;
	cin >> q;
	while (q--) solve();
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 61272 KB Output is correct
2 Correct 20 ms 61272 KB Output is correct
3 Incorrect 15 ms 61276 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 61276 KB Output is correct
2 Incorrect 14 ms 61252 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 61276 KB Output is correct
2 Incorrect 14 ms 61252 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 61276 KB Output is correct
2 Incorrect 14 ms 61252 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 61276 KB Output is correct
2 Incorrect 14 ms 61252 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 61276 KB Output is correct
2 Correct 14 ms 61272 KB Output is correct
3 Correct 16 ms 61276 KB Output is correct
4 Incorrect 18 ms 61276 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 61272 KB Output is correct
2 Correct 20 ms 61272 KB Output is correct
3 Incorrect 15 ms 61276 KB Output isn't correct
4 Halted 0 ms 0 KB -