| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 167273 |
2019-12-07T07:24:56 Z |
maruii |
Mergers (JOI19_mergers) |
C++14 |
|
110 ms |
37872 KB |
#include <bits/stdc++.h>
using namespace std;
vector<int> edge[500005], vec[500005];
int dfn[500005], dfnn, C[500005], par[500005], dep[500005];
bool A[500005];
struct UF {
int par[500005];
UF() { iota(par, par + 500005, 0); }
int fnd(int x) { return par[x] == x ? x : par[x] = fnd(par[x]); }
} u1, u2;
void dfs(int x, int p) {
par[x] = p;
dep[x] = dep[p] + 1;
dfn[x] = ++dfnn;
for (auto i : edge[x]) {
if (i == p) continue;
dfs(i, x);
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int N, M; cin >> N >> M;
for (int i = 1; i < N; ++i) {
int x, y; cin >> x >> y;
edge[x].push_back(y);
edge[y].push_back(x);
}
dfs(1, 1);
for (int i = 1; i <= N; ++i) {
cin >> C[i];
vec[C[i]].push_back(i);
}
for (int i = 1; i <= M; ++i) {
sort(vec[i].begin(), vec[i].end(), [&](int a, int b) {
return dfn[a] < dfn[b];
});
for (int j = 0; j + 1 < vec[i].size(); ++j) {
int x = u2.fnd(vec[i][j]), y = u2.fnd(vec[i][j + 1]);
while (x != y) {
int a, b;
if (dep[x] < dep[y]) {
u2.par[y] = u2.fnd(par[y]);
a = u1.fnd(C[par[y]]), b = u1.fnd(i);
y = u2.fnd(y);
}
else {
u2.par[x] = u2.fnd(par[x]);
a = u1.fnd(C[par[x]]), b = u1.fnd(i);
x = u2.fnd(x);
}
if (a != b) u1.par[a] = b;
}
}
}
int ans = 0;
for (int i = 1; i <= N; ++i) if (edge[i].size() == 1 && !A[u1.fnd(C[i])]) A[u1.fnd(C[i])] = 1, ans++;
cout << ans / 2;
return 0;
}
Compilation message
mergers.cpp: In function 'int main()':
mergers.cpp:41:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j + 1 < vec[i].size(); ++j) {
~~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
27896 KB |
Output is correct |
| 2 |
Correct |
29 ms |
27896 KB |
Output is correct |
| 3 |
Correct |
28 ms |
27772 KB |
Output is correct |
| 4 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 5 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 6 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 7 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 8 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 9 |
Correct |
32 ms |
27768 KB |
Output is correct |
| 10 |
Correct |
28 ms |
27740 KB |
Output is correct |
| 11 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 12 |
Incorrect |
28 ms |
27768 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
27896 KB |
Output is correct |
| 2 |
Correct |
29 ms |
27896 KB |
Output is correct |
| 3 |
Correct |
28 ms |
27772 KB |
Output is correct |
| 4 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 5 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 6 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 7 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 8 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 9 |
Correct |
32 ms |
27768 KB |
Output is correct |
| 10 |
Correct |
28 ms |
27740 KB |
Output is correct |
| 11 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 12 |
Incorrect |
28 ms |
27768 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
27896 KB |
Output is correct |
| 2 |
Correct |
29 ms |
27896 KB |
Output is correct |
| 3 |
Correct |
28 ms |
27772 KB |
Output is correct |
| 4 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 5 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 6 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 7 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 8 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 9 |
Correct |
32 ms |
27768 KB |
Output is correct |
| 10 |
Correct |
28 ms |
27740 KB |
Output is correct |
| 11 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 12 |
Incorrect |
28 ms |
27768 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
34896 KB |
Output is correct |
| 2 |
Incorrect |
110 ms |
37872 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
27896 KB |
Output is correct |
| 2 |
Correct |
29 ms |
27896 KB |
Output is correct |
| 3 |
Correct |
28 ms |
27772 KB |
Output is correct |
| 4 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 5 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 6 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 7 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 8 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 9 |
Correct |
32 ms |
27768 KB |
Output is correct |
| 10 |
Correct |
28 ms |
27740 KB |
Output is correct |
| 11 |
Correct |
28 ms |
27768 KB |
Output is correct |
| 12 |
Incorrect |
28 ms |
27768 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
