답안 #967125

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
967125	2024-04-21T07:36:19 Z	sleepntsheep	수도 (JOI20_capital_city)	C	100 / 100	371 ms	16304 KB

capital_city

#pragma GCC optimize("O3, unroll-loops")

#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;
/* graph */
int head[N], nxt[M_], vv[M_];

/* node with color */
int 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)
{
    visit[color[u]] = -1;
    ++dfreq[color[u]];
    par[u] = p;
    for (int j = head[u]; j; j = nxt[j])
    {
        if (vv[j] == p || dead[vv[j]])
            continue;
        dfs3(vv[j], u);
    }
}

void dfs4(int u, int p)
{
    visit[color[u]] = -1;
    dfreq[color[u]] = 0;
    for (int j = head[u]; j; j = nxt[j])
    {
        if (vv[j] == p || dead[vv[j]])
            continue;
        dfs4(vv[j], u);
    }
}

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);

    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:;
    }
    dfs4(u, u);

    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

capital_city.c:1:9: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    1 | #pragma GCC optimize("O3, unroll-loops")
      |         ^~~
capital_city.c:19:1: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   19 | {
      | ^
capital_city.c:28:1: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   28 | {
      | ^
capital_city.c:42:1: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   42 | {
      | ^
capital_city.c:55:1: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   55 | {
      | ^
capital_city.c:67:1: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   67 | {
      | ^
capital_city.c:75:1: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   75 | {
      | ^
capital_city.c: In function 'centroid_decomposition':
capital_city.c:89:18: warning: unused variable 'at' [-Wunused-variable]
   89 |         for (int at, jj = head_[col]; jj; jj = nxt_[jj])
      |                  ^~
capital_city.c: At top level:
capital_city.c:119:1: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
  119 | {
      | ^
capital_city.c: In function 'main':
capital_city.c:120:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |     scanf("%d%d", &n, &k);
      |     ^~~~~~~~~~~~~~~~~~~~~
capital_city.c:124:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         scanf("%d%d", &u, &v); --u, --v;
      |         ^~~~~~~~~~~~~~~~~~~~~
capital_city.c:130:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         scanf("%d", color+i);
      |         ^~~~~~~~~~~~~~~~~~~~

Subtask #1

1.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	10588 KB	Output is correct
2	Correct	2 ms	10588 KB	Output is correct
3	Correct	1 ms	10588 KB	Output is correct
4	Correct	1 ms	10672 KB	Output is correct
5	Correct	2 ms	10588 KB	Output is correct
6	Correct	1 ms	10588 KB	Output is correct
7	Correct	2 ms	10588 KB	Output is correct
8	Correct	1 ms	10588 KB	Output is correct
9	Correct	1 ms	10588 KB	Output is correct
10	Correct	1 ms	6492 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	10588 KB	Output is correct
2	Correct	2 ms	10588 KB	Output is correct
3	Correct	1 ms	10588 KB	Output is correct
4	Correct	1 ms	10672 KB	Output is correct
5	Correct	2 ms	10588 KB	Output is correct
6	Correct	1 ms	10588 KB	Output is correct
7	Correct	2 ms	10588 KB	Output is correct
8	Correct	1 ms	10588 KB	Output is correct
9	Correct	1 ms	10588 KB	Output is correct
10	Correct	1 ms	6492 KB	Output is correct
11	Correct	3 ms	10588 KB	Output is correct
12	Correct	2 ms	10588 KB	Output is correct
13	Correct	2 ms	10588 KB	Output is correct
14	Correct	3 ms	10588 KB	Output is correct
15	Correct	3 ms	10588 KB	Output is correct
16	Correct	3 ms	10588 KB	Output is correct
17	Correct	3 ms	10588 KB	Output is correct
18	Correct	3 ms	10588 KB	Output is correct
19	Correct	3 ms	10588 KB	Output is correct
20	Correct	2 ms	10588 KB	Output is correct
21	Correct	3 ms	10588 KB	Output is correct
22	Correct	3 ms	10588 KB	Output is correct
23	Correct	2 ms	10588 KB	Output is correct
24	Correct	2 ms	10588 KB	Output is correct
25	Correct	3 ms	10588 KB	Output is correct
26	Correct	3 ms	10588 KB	Output is correct
27	Correct	3 ms	10588 KB	Output is correct
28	Correct	3 ms	10588 KB	Output is correct
29	Correct	3 ms	10588 KB	Output is correct
30	Correct	3 ms	10588 KB	Output is correct

Subtask #3

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	238 ms	15952 KB	Output is correct
2	Correct	114 ms	16256 KB	Output is correct
3	Correct	212 ms	16028 KB	Output is correct
4	Correct	117 ms	16156 KB	Output is correct
5	Correct	213 ms	15188 KB	Output is correct
6	Correct	161 ms	16040 KB	Output is correct
7	Correct	223 ms	15536 KB	Output is correct
8	Correct	114 ms	16304 KB	Output is correct
9	Correct	296 ms	15008 KB	Output is correct
10	Correct	292 ms	14420 KB	Output is correct
11	Correct	371 ms	15020 KB	Output is correct
12	Correct	276 ms	16044 KB	Output is correct
13	Correct	283 ms	14304 KB	Output is correct
14	Correct	282 ms	15916 KB	Output is correct
15	Correct	304 ms	15956 KB	Output is correct
16	Correct	289 ms	14560 KB	Output is correct
17	Correct	303 ms	14716 KB	Output is correct
18	Correct	302 ms	14732 KB	Output is correct
19	Correct	298 ms	15792 KB	Output is correct
20	Correct	296 ms	16296 KB	Output is correct
21	Correct	1 ms	6492 KB	Output is correct

Subtask #4

59.0 / 59.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	10588 KB	Output is correct
2	Correct	2 ms	10588 KB	Output is correct
3	Correct	1 ms	10588 KB	Output is correct
4	Correct	1 ms	10672 KB	Output is correct
5	Correct	2 ms	10588 KB	Output is correct
6	Correct	1 ms	10588 KB	Output is correct
7	Correct	2 ms	10588 KB	Output is correct
8	Correct	1 ms	10588 KB	Output is correct
9	Correct	1 ms	10588 KB	Output is correct
10	Correct	1 ms	6492 KB	Output is correct
11	Correct	3 ms	10588 KB	Output is correct
12	Correct	2 ms	10588 KB	Output is correct
13	Correct	2 ms	10588 KB	Output is correct
14	Correct	3 ms	10588 KB	Output is correct
15	Correct	3 ms	10588 KB	Output is correct
16	Correct	3 ms	10588 KB	Output is correct
17	Correct	3 ms	10588 KB	Output is correct
18	Correct	3 ms	10588 KB	Output is correct
19	Correct	3 ms	10588 KB	Output is correct
20	Correct	2 ms	10588 KB	Output is correct
21	Correct	3 ms	10588 KB	Output is correct
22	Correct	3 ms	10588 KB	Output is correct
23	Correct	2 ms	10588 KB	Output is correct
24	Correct	2 ms	10588 KB	Output is correct
25	Correct	3 ms	10588 KB	Output is correct
26	Correct	3 ms	10588 KB	Output is correct
27	Correct	3 ms	10588 KB	Output is correct
28	Correct	3 ms	10588 KB	Output is correct
29	Correct	3 ms	10588 KB	Output is correct
30	Correct	3 ms	10588 KB	Output is correct
31	Correct	238 ms	15952 KB	Output is correct
32	Correct	114 ms	16256 KB	Output is correct
33	Correct	212 ms	16028 KB	Output is correct
34	Correct	117 ms	16156 KB	Output is correct
35	Correct	213 ms	15188 KB	Output is correct
36	Correct	161 ms	16040 KB	Output is correct
37	Correct	223 ms	15536 KB	Output is correct
38	Correct	114 ms	16304 KB	Output is correct
39	Correct	296 ms	15008 KB	Output is correct
40	Correct	292 ms	14420 KB	Output is correct
41	Correct	371 ms	15020 KB	Output is correct
42	Correct	276 ms	16044 KB	Output is correct
43	Correct	283 ms	14304 KB	Output is correct
44	Correct	282 ms	15916 KB	Output is correct
45	Correct	304 ms	15956 KB	Output is correct
46	Correct	289 ms	14560 KB	Output is correct
47	Correct	303 ms	14716 KB	Output is correct
48	Correct	302 ms	14732 KB	Output is correct
49	Correct	298 ms	15792 KB	Output is correct
50	Correct	296 ms	16296 KB	Output is correct
51	Correct	1 ms	6492 KB	Output is correct
52	Correct	186 ms	11860 KB	Output is correct
53	Correct	239 ms	11928 KB	Output is correct
54	Correct	200 ms	11924 KB	Output is correct
55	Correct	189 ms	11920 KB	Output is correct
56	Correct	202 ms	11684 KB	Output is correct
57	Correct	185 ms	11860 KB	Output is correct
58	Correct	166 ms	12420 KB	Output is correct
59	Correct	182 ms	12628 KB	Output is correct
60	Correct	275 ms	12476 KB	Output is correct
61	Correct	223 ms	12368 KB	Output is correct
62	Correct	113 ms	16208 KB	Output is correct
63	Correct	112 ms	16208 KB	Output is correct
64	Correct	114 ms	16220 KB	Output is correct
65	Correct	112 ms	16208 KB	Output is correct
66	Correct	131 ms	14296 KB	Output is correct
67	Correct	126 ms	14060 KB	Output is correct
68	Correct	129 ms	13904 KB	Output is correct
69	Correct	130 ms	14064 KB	Output is correct
70	Correct	139 ms	14040 KB	Output is correct
71	Correct	143 ms	14040 KB	Output is correct
72	Correct	125 ms	13904 KB	Output is correct
73	Correct	129 ms	13648 KB	Output is correct
74	Correct	131 ms	14004 KB	Output is correct
75	Correct	128 ms	14040 KB	Output is correct
76	Correct	201 ms	13648 KB	Output is correct
77	Correct	201 ms	13008 KB	Output is correct
78	Correct	284 ms	14508 KB	Output is correct
79	Correct	281 ms	13984 KB	Output is correct
80	Correct	294 ms	15956 KB	Output is correct
81	Correct	285 ms	15192 KB	Output is correct
82	Correct	293 ms	15124 KB	Output is correct
83	Correct	285 ms	14180 KB	Output is correct
84	Correct	311 ms	15700 KB	Output is correct
85	Correct	306 ms	15332 KB	Output is correct
86	Correct	275 ms	13908 KB	Output is correct
87	Correct	277 ms	14420 KB	Output is correct
88	Correct	280 ms	14676 KB	Output is correct
89	Correct	267 ms	13648 KB	Output is correct
90	Correct	270 ms	13648 KB	Output is correct
91	Correct	272 ms	14120 KB	Output is correct
92	Correct	262 ms	13892 KB	Output is correct
93	Correct	277 ms	13652 KB	Output is correct
94	Correct	303 ms	13692 KB	Output is correct
95	Correct	277 ms	14112 KB	Output is correct
96	Correct	264 ms	13712 KB	Output is correct
97	Correct	283 ms	14420 KB	Output is correct