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 <stdio.h>
#define N 200000
#define M (2*N-2)
#define N_ N+1
#define M_ M+1
#define K N
int n, k, color[N], answer, head[N], nxt[M_], vv[M_], head_[K], nxt_[N_], vv_[N_];
void link(int*head, int*nxt, int*vv, int*i, int u, int v)
{
nxt[i[0]] = head[u];
vv[i[0]] = v;
head[u] = i[0]++;
}
int dead[N], sz[N];
void dfs2(int u, int p)
{
sz[u] = 1;
for (int j = head[u]; j; j = nxt[j])
{
if (vv[j] == p || dead[vv[j]])
continue;
dfs2(vv[j], u);
sz[u] += sz[vv[j]];
}
}
int par[N], visit[K], dfreq[K], cfreq[K];
void dfs3(int u, int p, int delta)
{
visit[color[u]] = -1;
dfreq[color[u]] += delta;
par[u] = p;
for (int j = head[u]; j; j = nxt[j])
{
if (vv[j] == p || dead[vv[j]])
continue;
dfs3(vv[j], u, delta);
}
}
int get_centroid(int u, int p, int tsize)
{
for (int j = head[u]; j; j = nxt[j])
if (!dead[vv[j]] && vv[j] != p && sz[vv[j]] * 2 >= tsize)
return get_centroid(vv[j], u, tsize);
return u;
}
void centroid_decomposition(int u)
{
dfs2(u, u);
u = get_centroid(u, u, sz[u]);
dead[u] = 1;
dfs3(u, u, 1);
int col = color[u];
if (dfreq[col] == cfreq[col])
{
static int qu[N], head, tail;
head = tail = 0;
int dcolor = 0;
for (int at, jj = head_[col]; jj; jj = nxt_[jj])
qu[head++] = vv_[jj];
visit[col] = 1;
while (head-tail)
{
int uu = qu[tail++];
if (uu == u || visit[color[par[uu]]] == 1)
continue;
int nextcol = color[par[uu]];
if (cfreq[nextcol] != dfreq[nextcol])
goto NOTOK;
++dcolor;
for (int jj = head_[nextcol]; jj; jj = nxt_[jj])
qu[head++] = vv_[jj];
visit[nextcol] = 1;
}
if (dcolor < answer)
answer = dcolor;
NOTOK:;
}
dfs3(u, u, -1);
for (int j = head[u]; j; j = nxt[j])
if (!dead[vv[j]])
centroid_decomposition(vv[j]);
}
int main()
{
scanf("%d%d", &n, &k);
answer = n;
for (int i = 1, u, v, eo[1] = { 1 }; i < n; ++i)
{
scanf("%d%d", &u, &v); --u, --v;
link(head, nxt, vv, eo, u, v);
link(head, nxt, vv, eo, v, u);
}
for (int eo[1] = { 1 }, i = 0; i < n; ++i)
{
scanf("%d", color+i);
++cfreq[--color[i]];
link(head_, nxt_, vv_, eo, color[i], i);
}
centroid_decomposition(0);
printf("%d", answer);
}
Compilation message (stderr)
capital_city.c: In function 'centroid_decomposition':
capital_city.c:70:18: warning: unused variable 'at' [-Wunused-variable]
70 | for (int at, jj = head_[col]; jj; jj = nxt_[jj])
| ^~
capital_city.c: In function 'main':
capital_city.c:101:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | scanf("%d%d", &n, &k);
| ^~~~~~~~~~~~~~~~~~~~~
capital_city.c:105:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
105 | scanf("%d%d", &u, &v); --u, --v;
| ^~~~~~~~~~~~~~~~~~~~~
capital_city.c:111:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
111 | scanf("%d", color+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... |