oj.uz

Submission #1015976

# Submission time Handle Problem Language Result Execution time Memory
1015976 2024-07-07T07:35:59 Z vjudge3 Jail (JOI22_jail) C++17
100 / 100
 1231 ms 393812 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], in[120005], out[120005];
bool 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] = in[i] = out[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 (int i = 0; i < m; i++) {
		auto& [s, t] = path[i];
		cin >> s >> t;
		out[s] = i+1;
		in[t] = i+1;
	}
	for (int i = 0; i < m; i++) {
		auto [s, t] = path[i];
		if (in[s]) add(in[s], 0, i+1, 0);
		if (out[t]) add(i+1, 0, out[t], 0);
	}
	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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 172244 KB Output is correct
2 Correct 69 ms 172340 KB Output is correct
3 Correct 82 ms 172380 KB Output is correct
4 Correct 89 ms 172628 KB Output is correct
5 Correct 109 ms 173140 KB Output is correct
6 Correct 76 ms 172628 KB Output is correct
7 Correct 74 ms 172628 KB Output is correct
8 Correct 73 ms 172628 KB Output is correct
9 Correct 185 ms 181072 KB Output is correct
10 Correct 592 ms 345168 KB Output is correct
11 Correct 80 ms 172512 KB Output is correct
12 Correct 131 ms 173416 KB Output is correct
13 Correct 760 ms 351120 KB Output is correct
14 Correct 839 ms 361816 KB Output is correct
15 Correct 1053 ms 375036 KB Output is correct
16 Correct 1163 ms 364884 KB Output is correct
17 Correct 808 ms 352048 KB Output is correct
18 Correct 759 ms 360532 KB Output is correct
19 Correct 755 ms 352080 KB Output is correct
20 Correct 813 ms 352080 KB Output is correct
21 Correct 945 ms 393812 KB Output is correct
22 Correct 751 ms 351056 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 172164 KB Output is correct
2 Correct 70 ms 172368 KB Output is correct
3 Correct 73 ms 172620 KB Output is correct
4 Correct 73 ms 172624 KB Output is correct
5 Correct 74 ms 172572 KB Output is correct
6 Correct 75 ms 172624 KB Output is correct
7 Correct 73 ms 172608 KB Output is correct
8 Correct 73 ms 172536 KB Output is correct
9 Correct 78 ms 172880 KB Output is correct
10 Correct 85 ms 172628 KB Output is correct
11 Correct 72 ms 172460 KB Output is correct
12 Correct 69 ms 172368 KB Output is correct
13 Correct 73 ms 172372 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 172164 KB Output is correct
2 Correct 70 ms 172368 KB Output is correct
3 Correct 73 ms 172620 KB Output is correct
4 Correct 73 ms 172624 KB Output is correct
5 Correct 74 ms 172572 KB Output is correct
6 Correct 75 ms 172624 KB Output is correct
7 Correct 73 ms 172608 KB Output is correct
8 Correct 73 ms 172536 KB Output is correct
9 Correct 78 ms 172880 KB Output is correct
10 Correct 85 ms 172628 KB Output is correct
11 Correct 72 ms 172460 KB Output is correct
12 Correct 69 ms 172368 KB Output is correct
13 Correct 73 ms 172372 KB Output is correct
14 Correct 75 ms 172452 KB Output is correct
15 Correct 71 ms 172384 KB Output is correct
16 Correct 74 ms 172624 KB Output is correct
17 Correct 70 ms 172628 KB Output is correct
18 Correct 80 ms 172628 KB Output is correct
19 Correct 70 ms 172392 KB Output is correct
20 Correct 80 ms 172872 KB Output is correct
21 Correct 74 ms 172624 KB Output is correct
22 Correct 75 ms 172624 KB Output is correct
23 Correct 74 ms 172372 KB Output is correct
24 Correct 72 ms 172488 KB Output is correct
25 Correct 75 ms 172628 KB Output is correct
26 Correct 71 ms 172368 KB Output is correct
27 Correct 75 ms 172628 KB Output is correct
28 Correct 70 ms 172372 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 172164 KB Output is correct
2 Correct 70 ms 172368 KB Output is correct
3 Correct 73 ms 172620 KB Output is correct
4 Correct 73 ms 172624 KB Output is correct
5 Correct 74 ms 172572 KB Output is correct
6 Correct 75 ms 172624 KB Output is correct
7 Correct 73 ms 172608 KB Output is correct
8 Correct 73 ms 172536 KB Output is correct
9 Correct 78 ms 172880 KB Output is correct
10 Correct 85 ms 172628 KB Output is correct
11 Correct 72 ms 172460 KB Output is correct
12 Correct 69 ms 172368 KB Output is correct
13 Correct 73 ms 172372 KB Output is correct
14 Correct 75 ms 172452 KB Output is correct
15 Correct 71 ms 172384 KB Output is correct
16 Correct 74 ms 172624 KB Output is correct
17 Correct 70 ms 172628 KB Output is correct
18 Correct 80 ms 172628 KB Output is correct
19 Correct 70 ms 172392 KB Output is correct
20 Correct 80 ms 172872 KB Output is correct
21 Correct 74 ms 172624 KB Output is correct
22 Correct 75 ms 172624 KB Output is correct
23 Correct 74 ms 172372 KB Output is correct
24 Correct 72 ms 172488 KB Output is correct
25 Correct 75 ms 172628 KB Output is correct
26 Correct 71 ms 172368 KB Output is correct
27 Correct 75 ms 172628 KB Output is correct
28 Correct 70 ms 172372 KB Output is correct
29 Correct 76 ms 172616 KB Output is correct
30 Correct 77 ms 172624 KB Output is correct
31 Correct 75 ms 172580 KB Output is correct
32 Correct 74 ms 172652 KB Output is correct
33 Correct 77 ms 172564 KB Output is correct
34 Correct 71 ms 172624 KB Output is correct
35 Correct 71 ms 172624 KB Output is correct
36 Correct 72 ms 172628 KB Output is correct
37 Correct 73 ms 172628 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 172164 KB Output is correct
2 Correct 70 ms 172368 KB Output is correct
3 Correct 73 ms 172620 KB Output is correct
4 Correct 73 ms 172624 KB Output is correct
5 Correct 74 ms 172572 KB Output is correct
6 Correct 75 ms 172624 KB Output is correct
7 Correct 73 ms 172608 KB Output is correct
8 Correct 73 ms 172536 KB Output is correct
9 Correct 78 ms 172880 KB Output is correct
10 Correct 85 ms 172628 KB Output is correct
11 Correct 72 ms 172460 KB Output is correct
12 Correct 69 ms 172368 KB Output is correct
13 Correct 73 ms 172372 KB Output is correct
14 Correct 75 ms 172452 KB Output is correct
15 Correct 71 ms 172384 KB Output is correct
16 Correct 74 ms 172624 KB Output is correct
17 Correct 70 ms 172628 KB Output is correct
18 Correct 80 ms 172628 KB Output is correct
19 Correct 70 ms 172392 KB Output is correct
20 Correct 80 ms 172872 KB Output is correct
21 Correct 74 ms 172624 KB Output is correct
22 Correct 75 ms 172624 KB Output is correct
23 Correct 74 ms 172372 KB Output is correct
24 Correct 72 ms 172488 KB Output is correct
25 Correct 75 ms 172628 KB Output is correct
26 Correct 71 ms 172368 KB Output is correct
27 Correct 75 ms 172628 KB Output is correct
28 Correct 70 ms 172372 KB Output is correct
29 Correct 76 ms 172616 KB Output is correct
30 Correct 77 ms 172624 KB Output is correct
31 Correct 75 ms 172580 KB Output is correct
32 Correct 74 ms 172652 KB Output is correct
33 Correct 77 ms 172564 KB Output is correct
34 Correct 71 ms 172624 KB Output is correct
35 Correct 71 ms 172624 KB Output is correct
36 Correct 72 ms 172628 KB Output is correct
37 Correct 73 ms 172628 KB Output is correct
38 Correct 206 ms 180992 KB Output is correct
39 Correct 589 ms 345208 KB Output is correct
40 Correct 177 ms 183376 KB Output is correct
41 Correct 145 ms 181332 KB Output is correct
42 Correct 147 ms 182248 KB Output is correct
43 Correct 173 ms 183124 KB Output is correct
44 Correct 84 ms 173648 KB Output is correct
45 Correct 434 ms 344188 KB Output is correct
46 Correct 450 ms 344144 KB Output is correct
47 Correct 529 ms 352084 KB Output is correct
48 Correct 554 ms 351824 KB Output is correct
49 Correct 494 ms 349420 KB Output is correct
50 Correct 421 ms 349520 KB Output is correct
51 Correct 516 ms 352932 KB Output is correct
52 Correct 527 ms 352884 KB Output is correct
53 Correct 107 ms 185168 KB Output is correct
54 Correct 643 ms 343900 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 172384 KB Output is correct
2 Correct 91 ms 172360 KB Output is correct
3 Correct 71 ms 172372 KB Output is correct
4 Correct 72 ms 172372 KB Output is correct
5 Correct 77 ms 172392 KB Output is correct
6 Correct 89 ms 172368 KB Output is correct
7 Correct 81 ms 172624 KB Output is correct
8 Correct 71 ms 172372 KB Output is correct
9 Correct 73 ms 172276 KB Output is correct
10 Correct 73 ms 172372 KB Output is correct
11 Correct 71 ms 172384 KB Output is correct
12 Correct 78 ms 172724 KB Output is correct
13 Correct 106 ms 172880 KB Output is correct
14 Correct 111 ms 173140 KB Output is correct
15 Correct 109 ms 173032 KB Output is correct
16 Correct 558 ms 343584 KB Output is correct
17 Correct 731 ms 354904 KB Output is correct
18 Correct 875 ms 368204 KB Output is correct
19 Correct 502 ms 345164 KB Output is correct
20 Correct 551 ms 344880 KB Output is correct
21 Correct 501 ms 345024 KB Output is correct
22 Correct 594 ms 353212 KB Output is correct
23 Correct 578 ms 351916 KB Output is correct
24 Correct 594 ms 351944 KB Output is correct
25 Correct 589 ms 352132 KB Output is correct
26 Correct 578 ms 351948 KB Output is correct
27 Correct 657 ms 362692 KB Output is correct
28 Correct 666 ms 364224 KB Output is correct
29 Correct 660 ms 361156 KB Output is correct
30 Correct 586 ms 355272 KB Output is correct
31 Correct 661 ms 356804 KB Output is correct
32 Correct 609 ms 355488 KB Output is correct
33 Correct 587 ms 357576 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 172244 KB Output is correct
2 Correct 69 ms 172340 KB Output is correct
3 Correct 82 ms 172380 KB Output is correct
4 Correct 89 ms 172628 KB Output is correct
5 Correct 109 ms 173140 KB Output is correct
6 Correct 76 ms 172628 KB Output is correct
7 Correct 74 ms 172628 KB Output is correct
8 Correct 73 ms 172628 KB Output is correct
9 Correct 185 ms 181072 KB Output is correct
10 Correct 592 ms 345168 KB Output is correct
11 Correct 80 ms 172512 KB Output is correct
12 Correct 131 ms 173416 KB Output is correct
13 Correct 760 ms 351120 KB Output is correct
14 Correct 839 ms 361816 KB Output is correct
15 Correct 1053 ms 375036 KB Output is correct
16 Correct 1163 ms 364884 KB Output is correct
17 Correct 808 ms 352048 KB Output is correct
18 Correct 759 ms 360532 KB Output is correct
19 Correct 755 ms 352080 KB Output is correct
20 Correct 813 ms 352080 KB Output is correct
21 Correct 945 ms 393812 KB Output is correct
22 Correct 751 ms 351056 KB Output is correct
23 Correct 69 ms 172164 KB Output is correct
24 Correct 70 ms 172368 KB Output is correct
25 Correct 73 ms 172620 KB Output is correct
26 Correct 73 ms 172624 KB Output is correct
27 Correct 74 ms 172572 KB Output is correct
28 Correct 75 ms 172624 KB Output is correct
29 Correct 73 ms 172608 KB Output is correct
30 Correct 73 ms 172536 KB Output is correct
31 Correct 78 ms 172880 KB Output is correct
32 Correct 85 ms 172628 KB Output is correct
33 Correct 72 ms 172460 KB Output is correct
34 Correct 69 ms 172368 KB Output is correct
35 Correct 73 ms 172372 KB Output is correct
36 Correct 75 ms 172452 KB Output is correct
37 Correct 71 ms 172384 KB Output is correct
38 Correct 74 ms 172624 KB Output is correct
39 Correct 70 ms 172628 KB Output is correct
40 Correct 80 ms 172628 KB Output is correct
41 Correct 70 ms 172392 KB Output is correct
42 Correct 80 ms 172872 KB Output is correct
43 Correct 74 ms 172624 KB Output is correct
44 Correct 75 ms 172624 KB Output is correct
45 Correct 74 ms 172372 KB Output is correct
46 Correct 72 ms 172488 KB Output is correct
47 Correct 75 ms 172628 KB Output is correct
48 Correct 71 ms 172368 KB Output is correct
49 Correct 75 ms 172628 KB Output is correct
50 Correct 70 ms 172372 KB Output is correct
51 Correct 76 ms 172616 KB Output is correct
52 Correct 77 ms 172624 KB Output is correct
53 Correct 75 ms 172580 KB Output is correct
54 Correct 74 ms 172652 KB Output is correct
55 Correct 77 ms 172564 KB Output is correct
56 Correct 71 ms 172624 KB Output is correct
57 Correct 71 ms 172624 KB Output is correct
58 Correct 72 ms 172628 KB Output is correct
59 Correct 73 ms 172628 KB Output is correct
60 Correct 206 ms 180992 KB Output is correct
61 Correct 589 ms 345208 KB Output is correct
62 Correct 177 ms 183376 KB Output is correct
63 Correct 145 ms 181332 KB Output is correct
64 Correct 147 ms 182248 KB Output is correct
65 Correct 173 ms 183124 KB Output is correct
66 Correct 84 ms 173648 KB Output is correct
67 Correct 434 ms 344188 KB Output is correct
68 Correct 450 ms 344144 KB Output is correct
69 Correct 529 ms 352084 KB Output is correct
70 Correct 554 ms 351824 KB Output is correct
71 Correct 494 ms 349420 KB Output is correct
72 Correct 421 ms 349520 KB Output is correct
73 Correct 516 ms 352932 KB Output is correct
74 Correct 527 ms 352884 KB Output is correct
75 Correct 107 ms 185168 KB Output is correct
76 Correct 643 ms 343900 KB Output is correct
77 Correct 73 ms 172384 KB Output is correct
78 Correct 91 ms 172360 KB Output is correct
79 Correct 71 ms 172372 KB Output is correct
80 Correct 72 ms 172372 KB Output is correct
81 Correct 77 ms 172392 KB Output is correct
82 Correct 89 ms 172368 KB Output is correct
83 Correct 81 ms 172624 KB Output is correct
84 Correct 71 ms 172372 KB Output is correct
85 Correct 73 ms 172276 KB Output is correct
86 Correct 73 ms 172372 KB Output is correct
87 Correct 71 ms 172384 KB Output is correct
88 Correct 78 ms 172724 KB Output is correct
89 Correct 106 ms 172880 KB Output is correct
90 Correct 111 ms 173140 KB Output is correct
91 Correct 109 ms 173032 KB Output is correct
92 Correct 558 ms 343584 KB Output is correct
93 Correct 731 ms 354904 KB Output is correct
94 Correct 875 ms 368204 KB Output is correct
95 Correct 502 ms 345164 KB Output is correct
96 Correct 551 ms 344880 KB Output is correct
97 Correct 501 ms 345024 KB Output is correct
98 Correct 594 ms 353212 KB Output is correct
99 Correct 578 ms 351916 KB Output is correct
100 Correct 594 ms 351944 KB Output is correct
101 Correct 589 ms 352132 KB Output is correct
102 Correct 578 ms 351948 KB Output is correct
103 Correct 657 ms 362692 KB Output is correct
104 Correct 666 ms 364224 KB Output is correct
105 Correct 660 ms 361156 KB Output is correct
106 Correct 586 ms 355272 KB Output is correct
107 Correct 661 ms 356804 KB Output is correct
108 Correct 609 ms 355488 KB Output is correct
109 Correct 587 ms 357576 KB Output is correct
110 Correct 115 ms 173648 KB Output is correct
111 Correct 103 ms 173120 KB Output is correct
112 Correct 1065 ms 380808 KB Output is correct
113 Correct 648 ms 355004 KB Output is correct
114 Correct 759 ms 368840 KB Output is correct
115 Correct 367 ms 339096 KB Output is correct
116 Correct 605 ms 350992 KB Output is correct
117 Correct 904 ms 369532 KB Output is correct
118 Correct 501 ms 343832 KB Output is correct
119 Correct 484 ms 343792 KB Output is correct
120 Correct 103 ms 185424 KB Output is correct
121 Correct 759 ms 353708 KB Output is correct
122 Correct 732 ms 353216 KB Output is correct
123 Correct 717 ms 355664 KB Output is correct
124 Correct 807 ms 355664 KB Output is correct
125 Correct 747 ms 356180 KB Output is correct
126 Correct 1231 ms 372372 KB Output is correct
127 Correct 867 ms 392396 KB Output is correct
128 Correct 707 ms 384968 KB Output is correct
129 Correct 732 ms 358704 KB Output is correct
130 Correct 766 ms 386252 KB Output is correct