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;
vector<int> haha[200001];
vector<int> bruh[200001];
vector<int> col(200001);
vector<int> par(200001,-1);
vector<int> st(200001);
vector<int> wut(0);
vector<bool> yay(200001,1);
vector<bool> no(200001,1);
vector<bool> banana(200001,true);
void dfs(int a, int t, int t2) {
par[a] = t;
st[a] = 1;
wut.push_back(a);
for(int v: haha[a]) {
if(v != t && banana[v]) {
dfs(v,a,t2);
st[a]+=st[v];
}
}
}
int dude(int a, int t) {
// cout << a << endl;
int ans = INT_MAX;
int c = a;
dfs(a,0,t);
bool yeah = false;
while(!yeah) {
yeah = true;
for(int v: haha[c]) {
if(banana[v] && st[v]*2 >= st[a] && st[v] < st[c]) {
yeah = false;
c = v;
break;
}
}
}
// cout << a << " " << c << endl;
wut.clear();
dfs(c,0,t);
int br = -1,x = 0;
vector<int> wow(1,col[c]);
for(int i = 0; i < wow.size() && x == 0; i++) {
if(yay[wow[i]]) {
yay[wow[i]] = false;
br++;
for(int v: bruh[wow[i]]) {
if(par[v] == -1) {
x = 1;
break;
}
while(v != 0 && no[v]) {
no[v] = false;
wow.push_back(col[v]);
v = par[v];
}
}
}
}
if(x == 0) {
ans = min(ans,br);
}
for(int i = 0; i < wut.size(); i++) {
no[wut[i]]= true;
par[wut[i]] = -1;
}
for(int i = 0; i < wow.size(); i++) {
yay[wow[i]] = true;
}
banana[c] = false;
for(int v: haha[c]) {
if(banana[v]) {
ans = min(ans,dude(v,c));
}
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,k,a,b;
cin >> n >> k;
for(int i = 0; i < n-1; i++) {
cin >> a >> b;
haha[a].push_back(b);
haha[b].push_back(a);
}
for(int i = 1; i <= n; i++) {
cin >> col[i];
bruh[col[i]].push_back(i);
}
cout << dude(1,-1);
return 0;
}
Compilation message (stderr)
capital_city.cpp: In function 'int dude(int, int)':
capital_city.cpp:47:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i = 0; i < wow.size() && x == 0; i++) {
| ~~^~~~~~~~~~~~
capital_city.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i = 0; i < wut.size(); i++) {
| ~~^~~~~~~~~~~~
capital_city.cpp:71:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i = 0; i < wow.size(); i++) {
| ~~^~~~~~~~~~~~
# | 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... |