QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#109515 | #72. Mergers | bashkort# | 0 | 60ms | 25996kb | C++20 | 2.6kb | 2023-05-29 16:16:43 | 2024-05-31 13:47:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<vector<int>> adj(n);
vector<int> parent(n), jump(n), tin(n), tout(n), anc(k), col(n), depth(n);
for (int i = 1; i < n; ++i) {
int a, b;
cin >> a >> b;
a -= 1, b -= 1;
adj[a].push_back(b);
adj[b].push_back(a);
}
for (int i = 0; i < n; ++i) {
cin >> col[i];
--col[i];
anc[col[i]] = i;
}
auto dfs = [&](auto self, int v) -> void {
static int T = 0;
tin[v] = T++;
for (int to : adj[v]) {
if (to != parent[v]) {
parent[to] = v;
depth[to] = depth[v] + 1;
int p = jump[v], pp = jump[p];
if (depth[pp] - depth[p] == depth[p] - depth[v]) {
jump[to] = pp;
} else {
jump[to] = v;
}
self(self, to);
}
}
tout[v] = T;
};
dfs(dfs, 0);
auto isp = [&](int x, int y) {
return tin[x] <= tin[y] && tout[x] >= tout[y];
};
auto lca = [&](int x, int y) {
while (!isp(x, y)) {
if (!isp(jump[x], y)) {
x = jump[x];
} else {
x = parent[x];
}
}
return x;
};
for (int i = 0; i < n; ++i) {
anc[col[i]] = lca(anc[col[i]], i);
}
vector<int> fa(n);
iota(fa.begin(), fa.end(), 0);
auto leader = [&](int x) {
while (x != fa[x]) {
x = fa[x] = fa[fa[x]];
}
return x;
};
auto unite = [&](int x, int y) {
fa[leader(x)] = leader(y);
};
for (int i = 0; i < n; ++i) {
if (i != anc[col[i]]) {
int x = i, c = anc[col[i]];
while (!isp(x, c)) {
unite(x, parent[x]);
x = leader(x);
}
}
}
// cout << "here!" << endl;
vector<set<int>> st(n);
auto addEdge = [&](int x, int y) {
if (x == y) {
return;
}
// cout << x << "-" << y << endl;
st[x].insert(y);
st[y].insert(x);
};
for (int i = 1; i < n; ++i) {
addEdge(leader(i), leader(parent[i]));
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (leader(i) == i && st[i].size() <= 1) {
cnt += 1;
}
}
cout << cnt - 1 << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 10
Accepted
time: 0ms
memory: 3640kb
input:
1 1 1
output:
0
result:
ok single line: '0'
Test #2:
score: 10
Accepted
time: 0ms
memory: 3636kb
input:
3 2 2 1 3 1 2 2 1
output:
1
result:
ok single line: '1'
Test #3:
score: 10
Accepted
time: 1ms
memory: 3616kb
input:
5 2 1 2 4 5 4 2 3 4 2 1 2 1 2
output:
0
result:
ok single line: '0'
Test #4:
score: 10
Accepted
time: 0ms
memory: 3840kb
input:
7 7 5 7 4 7 6 4 1 3 2 6 3 4 6 7 2 4 5 3 1
output:
2
result:
ok single line: '2'
Test #5:
score: 10
Accepted
time: 1ms
memory: 3564kb
input:
10 5 1 3 9 6 8 6 3 10 3 2 1 6 8 7 2 5 9 4 1 1 3 2 2 5 3 1 4 2
output:
0
result:
ok single line: '0'
Test #6:
score: 10
Accepted
time: 0ms
memory: 3852kb
input:
100 1 7 97 63 10 65 17 26 85 50 92 92 20 28 83 92 51 5 4 56 2 18 27 16 73 24 78 73 10 35 6 49 10 20 11 42 23 30 7 24 69 38 87 53 45 25 3 93 57 64 47 84 73 20 91 97 31 99 45 20 38 76 9 98 94 40 72 77 38 37 7 88 8 37 78 73 8 90 61 45 68 32 29 55 37 46 88 17 14 46 12 83 100 35 40 71 20 32 92 57 88 92 6...
output:
0
result:
ok single line: '0'
Test #7:
score: 10
Accepted
time: 1ms
memory: 3648kb
input:
100 7 53 48 26 44 28 93 71 74 7 58 76 79 8 89 44 71 80 6 31 67 76 33 90 24 55 1 62 41 95 35 44 68 29 24 18 56 60 85 71 42 71 1 50 78 12 46 67 50 86 50 71 18 17 51 49 13 63 41 2 25 19 93 74 43 74 39 51 43 2 3 61 49 40 61 48 84 99 62 98 43 80 92 58 76 22 43 58 10 50 14 5 26 75 55 19 51 45 38 3 8 23 52...
output:
0
result:
ok single line: '0'
Test #8:
score: 10
Accepted
time: 1ms
memory: 3580kb
input:
9 6 7 6 9 1 2 4 4 5 9 2 8 6 9 3 8 1 3 1 6 4 4 2 5 5 6
output:
1
result:
ok single line: '1'
Test #9:
score: 10
Accepted
time: 1ms
memory: 3888kb
input:
100 6 45 58 90 65 28 24 76 32 97 92 50 81 38 17 98 40 81 21 68 56 36 78 45 12 74 31 72 30 20 35 61 85 39 8 69 40 54 60 80 25 5 95 95 27 54 70 19 21 20 12 85 93 16 88 95 48 46 14 45 72 40 7 37 14 72 47 22 10 45 31 75 69 32 6 73 22 56 99 11 35 43 55 1 56 15 56 35 42 100 55 49 34 76 33 87 45 78 70 90 8...
output:
1
result:
ok single line: '1'
Test #10:
score: 10
Accepted
time: 1ms
memory: 3648kb
input:
99 6 44 2 26 24 42 67 94 92 77 97 79 58 50 75 2 12 52 39 30 60 97 94 32 62 12 3 68 8 48 85 18 40 94 37 42 10 7 37 24 12 40 84 41 71 87 49 37 51 22 55 10 9 16 14 52 85 20 86 41 65 69 10 12 55 79 80 50 80 37 16 94 63 93 2 95 31 46 53 65 83 47 9 84 92 4 23 11 98 24 28 54 66 12 72 58 49 40 64 73 39 30 4...
output:
1
result:
ok single line: '1'
Test #11:
score: 0
Wrong Answer
time: 0ms
memory: 3648kb
input:
84 7 10 47 56 65 25 60 13 7 22 55 67 23 30 64 37 12 14 6 55 7 68 66 11 70 65 23 58 56 82 74 3 61 9 29 68 38 80 8 80 5 78 75 75 69 75 31 26 77 18 3 52 49 45 38 6 67 80 26 5 46 39 26 68 40 12 30 14 25 84 21 48 69 43 63 38 36 1 39 12 10 25 31 53 15 74 6 59 30 47 4 32 24 82 33 20 31 44 40 54 38 51 28 32...
output:
3
result:
wrong answer 1st lines differ - expected: '2', found: '3'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #66:
score: 0
Wrong Answer
time: 60ms
memory: 25996kb
input:
100000 100000 14957 4585 67467 70858 61843 47396 50630 17382 61027 39858 94990 21698 10240 22940 23505 67581 91432 14182 22040 40125 24556 60351 75822 41519 82801 23601 90653 29138 85096 34582 99587 59109 8932 45189 18235 36632 43160 14939 67600 76675 60175 65542 99294 53955 46429 66931 16822 48854 ...
output:
50082
result:
wrong answer 1st lines differ - expected: '25042', found: '50082'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%