#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int INF = 1e9;
struct segtree {
vector<int> T;
void upd(int idx, int s, int e, int p, int v) {
if(p < s || e < p) return;
if(s == e) {
T[idx] = v;
return;
}
int m = s+e >> 1;
upd(idx*2, s, m, p, v);
upd(idx*2+1, m+1, e, p, v);
T[idx] = max(T[idx*2], T[idx*2+1]);
}
int get(int idx, int s, int e, int l, int r) {
if(r < s || e < l) return -INF;
if(l <= s && e <= r) return T[idx];
int m = s+e >> 1;
return max(get(idx*2, s, m, l, r), get(idx*2+1, m+1, e, l, r));
}
void init(int N) {
T.resize(4*N, -INF);
}
};
int C[200009], O[200009], L[200009], R[200009], CR[200009], chk[200009];
vector<int> G[200009];
int main() {
int N, K; scanf("%d%d",&N,&K);
if(N == 1) return !printf("0");
for(int i=0; i<N-1; i++) {
int u, v; scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1; i<=N; i++) {
scanf("%d", &C[i]);
L[i] = N; R[i] = 1;
}
int x = -1, p = -1;
for(int i=1; i<=N; i++) if((int)G[i].size() == 1) x = i;
for(int i=1; i<=N; i++) {
O[i] = x;
for(auto& it: G[x]) if(it != p) {
p = x, x = it;
break;
}
}
for(int i=1; i<=N; i++) {
int c = C[O[i]];
L[c] = min(L[c], i);
R[c] = max(R[c], i);
}
for(int i=1; i<=K; i++) {
CR[L[i]] = R[i];
CR[R[i]] = L[i];
}
vector<pii> par;
segtree MXS, MNS;
MXS.init(N); MNS.init(N);
for(int i=N; i>=1; i--) {
if(!CR[i]) continue;
if(CR[i] >= i) {
int rm = max(MXS.get(1, 1, N, i, CR[i]), CR[i]);
int lm = min(-MNS.get(1, 1, N, i, rm), i);
if(lm == i) par.push_back({lm, rm});
MXS.upd(1, 1, N, i, rm);
}
if(CR[i] < i) MNS.upd(1, 1, N, i, -CR[i]);
}
int r = N, l = N+1, ans = INF, cnt = 0;
for(auto& it: par) {
int lm, rm; tie(lm, rm) = it;
while(lm < l) {
if(chk[C[O[l-1]]] == 0) ++cnt;
++chk[C[O[l-1]]]; --l;
}
while(rm < r) {
--chk[C[O[r]]];
if(chk[C[O[r]]] == 0) --cnt;
--r;
}
if(l == lm && r == rm) ans = min(ans, cnt - 1);
}
printf("%d", ans);
return 0;
}
Compilation message
capital_city.cpp: In member function 'void segtree::upd(int, int, int, int, int)':
capital_city.cpp:14:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
capital_city.cpp: In member function 'int segtree::get(int, int, int, int, int)':
capital_city.cpp:22:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
capital_city.cpp: In function 'int main()':
capital_city.cpp:34:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int N, K; scanf("%d%d",&N,&K);
~~~~~^~~~~~~~~~~~~~
capital_city.cpp:37:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int u, v; scanf("%d%d",&u,&v);
~~~~~^~~~~~~~~~~~~~
capital_city.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &C[i]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
4992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
4992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
255 ms |
22764 KB |
Output is correct |
| 2 |
Correct |
189 ms |
22808 KB |
Output is correct |
| 3 |
Correct |
257 ms |
22864 KB |
Output is correct |
| 4 |
Correct |
188 ms |
22740 KB |
Output is correct |
| 5 |
Correct |
258 ms |
22640 KB |
Output is correct |
| 6 |
Correct |
191 ms |
22780 KB |
Output is correct |
| 7 |
Correct |
248 ms |
22488 KB |
Output is correct |
| 8 |
Correct |
175 ms |
22512 KB |
Output is correct |
| 9 |
Incorrect |
216 ms |
22208 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
4992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
