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