//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> adj[maxn];
int c[maxn], dep[maxn], f[maxn];
pii ran[maxn];
void dfs(int n, int par, int d) {
dep[n] = d;
for (int v:adj[n]) {
if (v != par) {
dfs(v, n, d+1);
}
}
}
struct segtree{
int seg[4* maxn];
void modify(int cur, int l, int r, int ind, int val) {
if (r <= l) return;
if (r - l == 1) {
seg[cur] = val;
return;
}
int m = (l + r) / 2;
if (ind < m)modify(cur*2, l, m, ind, val);
else modify(cur*2+1, m, r, ind, val);
seg[cur] = min(seg[cur*2], seg[cur*2+1]);
}
int query(int cur, int l, int r, int ql, int qr) {
if (r <= l || ql >= r || qr <= l) return 1<<30;
if (ql <= l && qr >= r) {
return seg[cur];
}
int m = (l + r) / 2;
return min(query(cur*2, l, m, ql, qr), query(cur*2+1, m, r, ql, qr));
}
} tr, rig;
struct BIT{
int bit[maxn];
void modify(int ind, int val) {
if (ind == 0) return;
for (;ind < maxn;ind += ind & (-ind)) bit[ind] += val;
}
int query(int ind) {
int ret = 0;
for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
return ret;
}
} bit;
int prv[maxn];
int main() {
io
int n, K;
cin >> n >> K;
for (int i = 0;i < n - 1;i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1;i <= n;i++) {
if (adj[i].size() == 1) {
dfs(i, 0,1);
break;
}
}
for (int i = 1;i <= K;i++) ran[i] = {n+1, 0};
for (int i = 1;i <= n;i++) {
cin >> c[dep[i]];
ran[c[dep[i]]] = make_pair(min(ran[c[dep[i]]].ff, dep[i]), max(ran[c[dep[i]]].ss, dep[i]));
}
for (int i = 1;i <= K;i++) debug(ran[i].ff, ran[i].ss);
int ans = n+1;
for (int i = 1;i <= n;i++) {
int mi = tr.query(1, 1, n+1, ran[c[i]].ff, i);
f[i] = min(ran[c[i]].ff, mi);
tr.modify(1, 1, n+1, i, f[i]);
rig.modify(1, 1, n+1, i, -ran[c[i]].ss);
}
pary(f + 1, f + n + 1);
for (int i = 1;i <= n;i++) {
int r = -rig.query(1, 1, n+1, f[i], i+1);
bit.modify(prv[c[i]], -1);
bit.modify(i, 1);
prv[c[i]] = i;
if (i == ran[c[i]].ss && r <= i) {
ans = min(ans, bit.query(i) - bit.query(f[i] - 1) - 1);
}
}
cout << ans << endl;
}
Compilation message
capital_city.cpp: In function 'int main()':
capital_city.cpp:12:20: warning: statement has no effect [-Wunused-value]
12 | #define debug(...) 0
| ^
capital_city.cpp:88:29: note: in expansion of macro 'debug'
88 | for (int i = 1;i <= K;i++) debug(ran[i].ff, ran[i].ss);
| ^~~~~
capital_city.cpp:13:19: warning: statement has no effect [-Wunused-value]
13 | #define pary(...) 0
| ^
capital_city.cpp:97:2: note: in expansion of macro 'pary'
97 | pary(f + 1, f + n + 1);
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
204 ms |
24864 KB |
Output is correct |
| 2 |
Correct |
169 ms |
24908 KB |
Output is correct |
| 3 |
Correct |
202 ms |
24872 KB |
Output is correct |
| 4 |
Correct |
169 ms |
24792 KB |
Output is correct |
| 5 |
Correct |
200 ms |
24720 KB |
Output is correct |
| 6 |
Correct |
170 ms |
24908 KB |
Output is correct |
| 7 |
Correct |
195 ms |
24812 KB |
Output is correct |
| 8 |
Correct |
166 ms |
24748 KB |
Output is correct |
| 9 |
Correct |
221 ms |
24276 KB |
Output is correct |
| 10 |
Correct |
205 ms |
24404 KB |
Output is correct |
| 11 |
Correct |
207 ms |
24220 KB |
Output is correct |
| 12 |
Correct |
213 ms |
24272 KB |
Output is correct |
| 13 |
Correct |
199 ms |
24232 KB |
Output is correct |
| 14 |
Correct |
205 ms |
24268 KB |
Output is correct |
| 15 |
Correct |
204 ms |
24276 KB |
Output is correct |
| 16 |
Correct |
209 ms |
24224 KB |
Output is correct |
| 17 |
Correct |
201 ms |
24288 KB |
Output is correct |
| 18 |
Correct |
202 ms |
24268 KB |
Output is correct |
| 19 |
Correct |
204 ms |
24288 KB |
Output is correct |
| 20 |
Correct |
216 ms |
24312 KB |
Output is correct |
| 21 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
