oj.uz

Submission #1015967

# Submission time Handle Problem Language Result Execution time Memory
1015967 2024-07-07T07:13:18 Z vjudge3 Jail (JOI22_jail) C++17
0 / 100
 87 ms 172372 KB 
#include <bits/stdc++.h>
using namespace std;
 
vector<int> g[120005];
vector<pair<int, int>> h[360005][20];
int lift[120005][20], d[120005], tin[120005], tout[120005], timer, lg, col[360005][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 add(int u, int k, int v, int l) {
	h[u][k].push_back({v, l});
}
 
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++) lift[i][j] = 0;
	}
	for (int i = 1; i <= n*3; i++)
		for (int j = 0; j <= lg; j++) {
			h[i][j].clear();
			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 (int i = 1; i <= m; i++) {
		auto [u, v] = path[i-1];
		int t = lca(u, v);
		if (u != t && v != t) add(i, 0, n+t, 0);
		if (u != t && (u = lift[u][0]) != t) {
			int diff = d[u] - d[t], l = __lg(diff);
			add(i, 0, n+u, l);
			diff -= 1<<l;
			for (int j = 0; j <= lg; j++) if (diff & (1<<j)) u = lift[u][j];
			add(i, 0, n+u, l);
		}
		if (v != t) {
			int diff = d[v] - d[t], l = __lg(diff);
			add(i, 0, n+v, l);
			diff -= 1<<l;
			for (int j = 0; j <= lg; j++) if (diff & (1<<j)) v = lift[v][j];
			add(i, 0, n+v, l);
		}
	}
	for (int i = 1; i <= n; i++) for (int j = lg; j >= 1; j--) {
		add(n+i, j, n+i, j-1);
		if (lift[i][j-1]) add(n+i, j, n+lift[i][j-1], j-1);
	}
	for (int i = 0; i < m; i++) add(n+path[i].first, 0, i+1, 0);
	for (int i = 1; i <= m; i++) {
		auto [u, v] = path[i-1];
		int t = lca(u, v);
		if (u != t && v != t) add(n*2+t, 0, i, 0);
		if (u != t) {
			int diff = d[u] - d[t], l = __lg(diff);
			add(n*2+u, l, i, 0);
			diff -= 1<<l;
			for (int j = 0; j <= lg; j++) if (diff & (1<<j)) u = lift[u][j];
			add(n*2+u, l, i, 0);
		}
		if (v != t && (v = lift[v][0]) != t) {
			int diff = d[v] - d[t], l = __lg(diff);
			add(n*2+v, l, i, 0);
			diff -= 1<<l;
			for (int j = 0; j <= lg; j++) if (diff & (1<<j)) v = lift[v][j];
			add(n*2+v, l, i, 0);
		}
	}
	for (int i = 1; i <= n; i++) for (int j = lg; j >= 1; j--) {
		add(n*2+i, j-1, n*2+i, j);
		if (lift[i][j-1]) add(n*2+lift[i][j-1], j-1, n*2+i, j);
	}
	for (int i = 0; i < m; i++) add(i+1, 0, n*2+path[i].second, 0);
	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 69 ms 172368 KB Output is correct
2 Correct 74 ms 172308 KB Output is correct
3 Incorrect 69 ms 172116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 172372 KB Output is correct
2 Incorrect 71 ms 172372 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 172372 KB Output is correct
2 Incorrect 71 ms 172372 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 172372 KB Output is correct
2 Incorrect 71 ms 172372 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 172372 KB Output is correct
2 Incorrect 71 ms 172372 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 172368 KB Output is correct
2 Correct 78 ms 172360 KB Output is correct
3 Correct 70 ms 172304 KB Output is correct
4 Incorrect 73 ms 172116 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 172368 KB Output is correct
2 Correct 74 ms 172308 KB Output is correct
3 Incorrect 69 ms 172116 KB Output isn't correct
4 Halted 0 ms 0 KB -