#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
Draw a directed edge between city A and city B, if there lies a town of city B on the path between two
towns of city A.
Answer = (minimum size of any SCC with outdegree zero) - 1
*/
const int maxN = 200000;
int N, K;
vector<int> edge[1+maxN];
int col[1+maxN];
vector<int> col_count(1+maxN, 0);
int parent[1+maxN];
vector<int> order(1);
vector<int> order_index(1+maxN, 0);
vector<int> subtree(1+maxN, 1);
void dfs(int u)
{
order_index[u] = order.size();
order.push_back(u);
for(int v: edge[u])
{
if(order_index[v]) continue;
parent[v] = u;
dfs(v);
subtree[u] += subtree[v];
}
}
struct segtree
{
int l;
int r;
vector<int> v;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
if(l == r)
{
v.push_back(col[ order[l] ]);
}
else
{
int m = (l+r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
for(int x: left->v) v.push_back(x);
for(int x: right->v) v.push_back(x);
sort(v.begin(), v.end());
}
}
int count(int L, int R, int V)
{
if(R < l || r < L) return 0;
else if(L <= l && r <= R)
{
int i1 = -1, i2 = -1;
for(int bit = 18; bit >= 0; bit--)
{
if(i1 + (1 << bit) >= v.size()) continue;
if(v[i1 + (1 << bit)] >= V) continue;
i1 += (1 << bit);
}
i1++;
if(v[i1] != V) return 0;
for(int bit = 18; bit >= 0; bit--)
{
if(i2 + (1 << bit) >= v.size()) continue;
if(v[i2 + (1 << bit)] > V) continue;
i2 += (1 << bit);
}
return i2-i1+1;
}
else
{
return left->count(L, R, V) + right->count(L, R, V);
}
}
};
vector<int> newEdge[1+maxN];
vector<int> newEdgeRev[1+maxN];
vector<int> scc_dfs_order;
vector<int> visit(1+maxN, 0);
void scc_dfs_1(int u)
{
for(int v: newEdge[u])
{
if(visit[v]) continue;
visit[v] = 1;
scc_dfs_1(v);
}
scc_dfs_order.push_back(u);
}
int curr_ct;
vector<int> scc_size(1, 0);
vector<int> scc(1+maxN, 0);
int scc_count = 0;
void scc_dfs_2(int u)
{
scc_size[scc_count]++;
scc[u] = scc_count;
for(int v: newEdgeRev[u])
{
if(visit[v]) continue;
visit[v] = 1;
curr_ct++;
scc_dfs_2(v);
}
}
int main()
{
cin >> N >> K;
for(int i = 1; i <= N-1; i++)
{
int A, B;
cin >> A >> B;
edge[A].push_back(B);
edge[B].push_back(A);
}
for(int i = 1; i <= N; i++)
{
cin >> col[i];
col_count[ col[i] ]++;
}
parent[1] = 0;
dfs(1);
segtree S(1, N);
// for(int i = 1; i <= N; i++) cerr << order[i] << ' ';
// cerr << '\n';
// for(int i = 1; i <= N; i++) cerr << order_index[i] << ' ';
// cerr << '\n';
for(int i = 2; i <= N; i++)
{
if(col[i] == col[ parent[i] ]) continue;
int ct;
ct = S.count(order_index[i], order_index[i] + subtree[i] - 1, col[parent[i]]);
if(ct != col_count[ col[parent[i]] ] && ct != 0)
{
newEdge[ col[ parent[i] ] ].push_back(col[i]);
newEdgeRev[ col[i] ].push_back(col[ parent[i] ]);
}
ct = S.count(order_index[i], order_index[i] + subtree[i] - 1, col[i]);
if(ct != col_count[i] && ct != 0)
{
newEdge[ col[i] ].push_back(col[ parent[i] ]);
newEdgeRev[ col[parent[i]] ].push_back(col[i]);
}
}
for(int j = 1; j <= K; j++)
{
if(visit[j]) continue;
visit[j] = 1;
scc_dfs_1(j);
}
reverse(scc_dfs_order.begin(), scc_dfs_order.end());
// for(int j: scc_dfs_order) cerr << j << ' ';
// cerr << '\n';
visit = vector<int>(K+1, 0);
for(int j: scc_dfs_order)
{
if(visit[j]) continue;
scc_count++;
scc_size.push_back(0);
visit[j] = 1;
curr_ct = 1;
scc_dfs_2(j);
// cerr << j << ' ' << curr_ct << '\n';
}
vector<int> scc_outdegree(scc_count+1, 0);
for(int u = 1; u <= K; u++)
for(int v: newEdge[u])
if(scc[u] != scc[v])
scc_outdegree[ scc[u] ]++;
int res = 1e9;
for(int x = 1; x <= scc_count; x++)
if(scc_outdegree[x] == 0)
res = min(res, scc_size[x] - 1);
// for(int i = 1; i <= K; i++) cerr << scc[i] << ' ' << scc_outdegree[scc[i]] << ' ' << scc_size[scc[i]] << '\n';
// cerr << '\n';
cout << res << '\n';
}
Compilation message
capital_city.cpp: In member function 'int segtree::count(int, int, int)':
capital_city.cpp:91:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | if(i1 + (1 << bit) >= v.size()) continue;
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~
capital_city.cpp:101:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | if(i2 + (1 << bit) >= v.size()) continue;
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
18252 KB |
Output is correct |
| 2 |
Correct |
13 ms |
18308 KB |
Output is correct |
| 3 |
Correct |
14 ms |
18252 KB |
Output is correct |
| 4 |
Correct |
13 ms |
18240 KB |
Output is correct |
| 5 |
Correct |
13 ms |
18344 KB |
Output is correct |
| 6 |
Correct |
13 ms |
18340 KB |
Output is correct |
| 7 |
Incorrect |
13 ms |
18252 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
18252 KB |
Output is correct |
| 2 |
Correct |
13 ms |
18308 KB |
Output is correct |
| 3 |
Correct |
14 ms |
18252 KB |
Output is correct |
| 4 |
Correct |
13 ms |
18240 KB |
Output is correct |
| 5 |
Correct |
13 ms |
18344 KB |
Output is correct |
| 6 |
Correct |
13 ms |
18340 KB |
Output is correct |
| 7 |
Incorrect |
13 ms |
18252 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2134 ms |
101524 KB |
Output is correct |
| 2 |
Correct |
694 ms |
102080 KB |
Output is correct |
| 3 |
Incorrect |
1808 ms |
101340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
18252 KB |
Output is correct |
| 2 |
Correct |
13 ms |
18308 KB |
Output is correct |
| 3 |
Correct |
14 ms |
18252 KB |
Output is correct |
| 4 |
Correct |
13 ms |
18240 KB |
Output is correct |
| 5 |
Correct |
13 ms |
18344 KB |
Output is correct |
| 6 |
Correct |
13 ms |
18340 KB |
Output is correct |
| 7 |
Incorrect |
13 ms |
18252 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
