Submission #10715600


Source Code Expand

#include <bits/stdc++.h>

#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)

const int MaxN = 1e4 + 10;
const int inf = 0x3f3f3f3f;

struct edge
{
    int next, to;
};

char s[MaxN];
edge e[MaxN];
int n, ans, cnt;
int a[MaxN], head[MaxN], dis[MaxN], size[MaxN], f[MaxN];

void init()
{
    for (int i = 1; i <= n; i++)
        dis[i] = size[i] = f[i] = 0;
}

void add_edge(int u, int v)
{
    ++cnt;
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}

inline int read()
{
    int x = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0')
        ch = getchar();
    while (ch <= '9' && ch >= '0')
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}

void dfs(int u, int fa)
{
    size[u] = a[u];
    int maxp = 0;
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (v == fa) continue;
        dfs(v, u), size[u] += size[v], dis[v] += size[v];
        dis[u] += dis[v], maxp = ((dis[maxp] > dis[v]) ? maxp : v);
    }    
    if(!maxp) return (void) (f[u] = 0);
    if(dis[u] >= 2 * (dis[maxp])) f[u] = (dis[u] / 2);
    else f[u] = dis[u] - dis[maxp] + std::min(f[maxp], (2 * dis[maxp] - dis[u]) / 2);
}

int main()
{
    ans = inf;
    n = read(), scanf("%s", s + 1);
    for (int i = 1; i <= n; i++)
        a[i] = s[i] - '0';
    for (int i = 1; i < n; i++)
    {
        int u = read(), v = read();
        add_edge(u, v), add_edge(v, u);
    }
    for (int i = 1; i <= n; i++)
    {
        init(), dfs(i, 0);
        if(dis[i] & 1) continue;
        if (f[i] * 2 >= dis[i]) ans = std::min(ans, dis[i] / 2);
    }
    printf("%d\n", (ans == inf) ? -1 : ans);
    return 0;
}

Submission Info

Submission Time
Task E - Complete Compress
User little_sun
Language C++14 (GCC 5.4.1)
Score 1500
Code Size 1776 Byte
Status AC
Exec Time 84 ms
Memory 512 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:64:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     n = read(), scanf("%s", s + 1);
                                   ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1500 / 1500
Status
AC × 3
AC × 43
Set Name Test Cases
Sample example_00, example_01, example_02
All example_00, example_01, example_02, houki_00, houki_01, houki_02, houki_03, houki_04, houki_05, houki_06, houki_07, houki_08, houki_09, line_00, line_01, line_02, line_03, line_04, line_05, line_06, line_07, line_08, line_09, rand_00, rand_01, rand_02, rand_03, rand_04, rand_05, rand_06, rand_07, rand_08, rand_09, uni_00, uni_01, uni_02, uni_03, uni_04, uni_05, uni_06, uni_07, uni_08, uni_09
Case Name Status Exec Time Memory
example_00 AC 1 ms 256 KB
example_01 AC 1 ms 256 KB
example_02 AC 1 ms 256 KB
houki_00 AC 30 ms 384 KB
houki_01 AC 64 ms 384 KB
houki_02 AC 57 ms 384 KB
houki_03 AC 84 ms 384 KB
houki_04 AC 29 ms 384 KB
houki_05 AC 79 ms 384 KB
houki_06 AC 22 ms 384 KB
houki_07 AC 71 ms 384 KB
houki_08 AC 40 ms 384 KB
houki_09 AC 71 ms 384 KB
line_00 AC 64 ms 384 KB
line_01 AC 80 ms 512 KB
line_02 AC 39 ms 384 KB
line_03 AC 79 ms 512 KB
line_04 AC 24 ms 384 KB
line_05 AC 83 ms 512 KB
line_06 AC 55 ms 384 KB
line_07 AC 80 ms 512 KB
line_08 AC 32 ms 384 KB
line_09 AC 78 ms 512 KB
rand_00 AC 3 ms 256 KB
rand_01 AC 82 ms 384 KB
rand_02 AC 6 ms 256 KB
rand_03 AC 75 ms 384 KB
rand_04 AC 81 ms 384 KB
rand_05 AC 83 ms 384 KB
rand_06 AC 66 ms 384 KB
rand_07 AC 76 ms 384 KB
rand_08 AC 3 ms 256 KB
rand_09 AC 82 ms 384 KB
uni_00 AC 22 ms 384 KB
uni_01 AC 35 ms 384 KB
uni_02 AC 22 ms 384 KB
uni_03 AC 38 ms 384 KB
uni_04 AC 33 ms 384 KB
uni_05 AC 34 ms 384 KB
uni_06 AC 27 ms 384 KB
uni_07 AC 38 ms 384 KB
uni_08 AC 19 ms 256 KB
uni_09 AC 36 ms 384 KB