// Grzegorz Ryn
// V LO Kraków
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define st first
#define nd second
#define FOR(__VAR, __START, __END) for(int __VAR=__START; __VAR<=__END; __VAR++)
#define FORB(__VAR, __START, __END) for(int __VAR=__START; __VAR>=__END; __VAR--)
#define FORK(__VAR, __START, __END, __DIFF) for(int __VAR=__START; __VAR<=END; __VAR+=__DIFF)
#define all(__VAR) (__VAR).begin(), (__VAR).end()
#define rall(__VAR) (__VAR).rbegin(), (__VAR).rend()
#define DEBUG(__VAR) cout << #__VAR << ": " << __VAR << endl;
template<typename __T1, typename __T2>
ostream & operator<<(ostream &out, pair<__T1, __T2> &__VAR) {
cout << "[" << __VAR.st << ", " << __VAR.nd << "]";
return out;
}
template<typename __T>
ostream & operator<<(ostream &out, vector<__T> &__VAR) {
cout << "[";
FOR(i, 0, (int)__VAR.size()-2)
cout << __VAR[i] << ", ";
if(__VAR.size()>0)
cout << __VAR[__VAR.size()-1];
cout << "]" << endl;
return out;
}
const int INF=1e9;
int N, K, n = 1<<3;
vector<vector<int>> g, inv_g, tree;
vector<int> pre_order, c, siz, heavy, depth, head, parent;
vector<bool> vis;
void prep_hld(int v) {
vis[v] = true;
for(int u:tree[v]) {
if(vis[u]) {
continue;
}
depth[u] = depth[v]+1;
parent[u] = v;
prep_hld(u);
siz[v] += siz[u];
if(heavy[v] == -1 || siz[heavy[v]] < siz[u]) {
heavy[v] = u;
}
}
}
void get_ind(int v, int h) {
static int next_it = 0;
vis[v] = true;
pre_order[v] = next_it++;
head[v] = h;
if(heavy[v] != -1) {
get_ind(heavy[v], h);
}
for(int u:tree[v]) {
if(vis[u]) {
continue;
}
get_ind(u, u);
}
}
void get_input() {
cin >> N >> K;
tree.resize(N);
c.resize(N);
pre_order.resize(N);
parent.resize(N);
for(int i=0; i<N-1; i++) {
int a, b;
cin >> a >> b;
a--, b--;
tree[a].pb(b);
tree[b].pb(a);
}
for(int i=0; i<N; i++) {
cin >> c[i];
c[i]--;
}
vis.resize(N, false);
siz.resize(N, 1);
heavy.resize(N, -1);
head.resize(N, 0);
depth.resize(N, 0);
prep_hld(0);
fill(all(vis), false);
get_ind(0, 0);
g.resize(2*n + K);
for(int i=n-1; i>0; i--) {
g[i].pb(2*i);
g[i].pb(2*i+1);
}
for(int i=0; i<N; i++) {
g[pre_order[i] + n].pb(2*n + c[i]);
g[2*n + c[i]].pb(pre_order[i] + n);
}
}
void add(int l, int r, int v, int p, int q, int u) {
if(r<p || q<l) {
return;
}
if(p<=l && r<=q) {
g[u+n].pb(v);
return;
}
int mid = (l+r)/2;
add(l, mid, 2*v, p, q, u);
add(mid+1, r, 2*v+1, p, q, u);
}
int lca(int v, int u) {
while(head[u] != head[v]) {
if(depth[head[u]] < depth[head[v]]) {
swap(u, v);
}
u = parent[head[u]];
}
if(depth[u] > depth[v]) {
swap(u, v);
}
return u;
}
void update(int u, int v, int source) {
//cout << u << " -> " << v << endl;
while(head[u] != head[v]) {
//cout << pre_order[source] << " => [" << pre_order[head[u]] << ' ' << pre_order[u] << "]" << endl;
add(0, n-1, 1, pre_order[head[u]], pre_order[u], pre_order[source]);
u = parent[head[u]];
}
//cout << pre_order[source] << " => [" << pre_order[v] << ' ' << pre_order[u] << "]" << endl;
add(0, n-1, 1, pre_order[v], pre_order[u], pre_order[source]);
}
stack<int> s;
void dfs1(int v) {
vis[v] = true;
for(int u:g[v]) {
if(vis[u]) {
continue;
}
dfs1(u);
}
s.push(v);
}
vector<int> comp;
int next_comp = 0;
void dfs2(int v) {
vis[v] = true;
comp[v] = next_comp;
for(int u:inv_g[v]) {
if(vis[u]) {
continue;
}
dfs2(u);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
get_input();
vector<int> color_lca(K);
for(int i=0; i<N; i++) {
color_lca[c[i]] = i;
}
for(int i=0; i<N; i++) {
color_lca[c[i]] = lca(color_lca[c[i]], i);
}
for(int i=0; i<N; i++) {
update(i, color_lca[c[i]], i);
}
inv_g.resize(g.size());
for(int i=0; i<g.size(); i++) {
for(int u:g[i]) {
inv_g[u].pb(i);
}
}
vis.resize(g.size());
fill(all(vis), false);
for(int i=0; i<g.size(); i++) {
if(vis[i]) {
continue;
}
dfs1(i);
}
fill(all(vis), false);
comp.resize(g.size());
while(!s.empty()) {
int v=s.top();
s.pop();
if(vis[v]) {
continue;
}
dfs2(v);
next_comp++;
}
vector<int> out(next_comp, 0), siz(next_comp, 0);
for(int i=0; i<g.size(); i++) {
for(int j:g[i]) {
if(comp[i] != comp[j]) {
out[comp[i]]++;
}
}
}
for(int i=2*n; i<g.size(); i++) {
siz[comp[i]]++;
}
int result = INF;
for(int i=0; i<N; i++) {
int cmp = comp[pre_order[i]+n];
if(out[cmp] > 0) {
continue;
}
result = min(result, siz[cmp]-1);
}
cout << result << '\n';
return 0;
}
Compilation message
capital_city.cpp: In function 'int main()':
capital_city.cpp:212:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
212 | for(int i=0; i<g.size(); i++) {
| ~^~~~~~~~~
capital_city.cpp:220:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
220 | for(int i=0; i<g.size(); i++) {
| ~^~~~~~~~~
capital_city.cpp:240:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
240 | for(int i=0; i<g.size(); i++) {
| ~^~~~~~~~~
capital_city.cpp:247:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
247 | for(int i=2*n; i<g.size(); i++) {
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
148 ms |
72512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
