# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
169101 | Akashi | Mergers (JOI19_mergers) | C++14 | 12 ms | 12152 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int n, k;
int h[500005], cul[500005], up[500005], root[500005], nr[500005], nr2[500005];
bool viz[500005], tip[500005];
int d[500005][21];
vector <int> v[500005];
priority_queue <pair <int, int> > L;
void predfs(int nod = 1){
viz[nod] = 1;
bool leaf = true;
for(auto it : v[nod]){
if(viz[it]) continue ;
leaf = false;
h[it] = h[nod] + 1;
predfs(it);
d[it][0] = nod;
}
viz[nod] = 0;
if(leaf) L.push({h[nod], nod});
}
inline int lca(int x, int y){
if(h[x] < h[y]) swap(x, y);
int dif = h[x] - h[y];
int p = 1, k = 0;
while(dif){
if(dif & p) x = d[x][k], dif ^= p;
p = p << 1; ++k;
}
if(x == y) return x;
for(int t = 20; t >= 0 ; --t)
if(d[x][t] != d[y][t]) x = d[x][t], y = d[y][t];
return d[x][0];
}
int main()
{
freopen("1.in", "r", stdin);
scanf("%d%d", &n, &k);
int x, y;
for(int i = 1; i < n ; ++i){
scanf("%d%d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}
predfs();
for(int t = 1; t <= 20 ; ++t)
for(int i = 1; i <= n ; ++i)
d[i][t] = d[d[i][t - 1]][t - 1];
for(int i = 1; i <= n ; ++i){
scanf("%d", &x);
cul[i] = x;
if(root[x] == 0) root[x] = i;
else root[x] = lca(root[x], i);
}
for(int i = 1; i <= n ; ++i) up[i] = root[cul[i]];
int Sol = 0, NR = 0, ad = 0;
while(!L.empty()){
int nod = L.top().second;
L.pop();
bool leaf = true;
for(auto it : v[nod]){
if(it == d[nod][0]) continue ;
leaf = false;
nr[nod] += nr[it] + nr2[it];
}
int TT = d[nod][0];
tip[TT] = max(tip[nod], tip[TT]);
if(up[nod] != nod) up[TT] = lca(up[nod], up[TT]);
else{
++NR;
if(!tip[nod]){
tip[TT] = 1, nr[nod] = 1;
++ad;
}
}
if(nr[nod] > 1){
Sol = Sol + (nr[nod] - 1) / 2;
if(nr[nod] % 2 == 0) nr2[nod] = 1;
nr[nod] = 1;
}
if(!viz[TT] && TT != 1){
viz[TT] = 1;
L.push({h[TT], TT});
}
}
// cerr << ad << endl;
if(NR == 0) printf("0");
else{
int n1 = 0, n2 = 0;
int cnt = 0;
for(auto it : v[1]){
n1 += nr[it];
n2 += nr2[it];
if(nr[it]) ++cnt;
}
if(cnt > 1) Sol = Sol + (n1 + n2) / 2 + (n1 + n2) % 2;
else Sol = Sol + n1 / 2 + n1 % 2 + n2 / 2 + n2 % 2;
printf("%d", Sol);
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |