Submission #19896415

Source Code Expand

#include <bits/stdc++.h>

using namespace std; const int maxn = 5e3 + 1e2; typedef long long ll;

char s[maxn]; vector<int> T[maxn]; ll dp[maxn], sum[maxn], sze[maxn];

void DFS(int u, int fa)
{
	sze[u] = s[u] - '0', sum[u] = 0; ll maxx = 0;
	for (int v : T[u]) if (v != fa) DFS(v, u), sum[u] += sum[v], maxx = max(maxx, sum[v]), sze[u] += sze[v];
	if (maxx * 2 < sum[u]) dp[u] = sum[u] / 2;
	else
	{
		int pt = 0; for (int v : T[u]) if (v != fa) if (sum[v] > sum[pt]) pt = v;
		dp[u] = sum[u] - maxx + min(dp[pt], (2 * maxx - sum[u]) / 2);
	}
	sum[u] += sze[u];
}

int n; int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cin >> n;
	cin >> s + 1; for (int i = 1, u, v; i < n; i++) cin >> u >> v, T[u].push_back(v), T[v].push_back(u);
	ll ans = 1e18; for (int i = 1; i <= n; i++)
	{
		DFS(i, 0); if (dp[i] == (sum[i] - sze[i]) / 2 && (sum[i] - sze[i]) % 2 == 0) ans = min(ans, dp[i]);
	}
	if (ans == 1e18) cout << -1 << endl; else cout << ans << endl;
}

Submission Info

Submission Time
Task E - Complete Compress
User Linshey
Language C++ (GCC 9.2.1)
Score 1500
Code Size 984 Byte
Status AC
Exec Time 104 ms
Memory 3864 KiB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:24:11: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   24 |  cin >> s + 1; for (int i = 1, u, v; i < n; i++) cin >> u >> v, T[u].push_back(v), T[v].push_back(u);
      |         ~~^~~

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 8 ms 3588 KiB
example_01 AC 2 ms 3592 KiB
example_02 AC 2 ms 3520 KiB
houki_00 AC 42 ms 3736 KiB
houki_01 AC 70 ms 3788 KiB
houki_02 AC 63 ms 3624 KiB
houki_03 AC 101 ms 3656 KiB
houki_04 AC 42 ms 3648 KiB
houki_05 AC 87 ms 3732 KiB
houki_06 AC 38 ms 3628 KiB
houki_07 AC 82 ms 3692 KiB
houki_08 AC 56 ms 3716 KiB
houki_09 AC 76 ms 3620 KiB
line_00 AC 71 ms 3784 KiB
line_01 AC 86 ms 3828 KiB
line_02 AC 50 ms 3768 KiB
line_03 AC 89 ms 3864 KiB
line_04 AC 33 ms 3676 KiB
line_05 AC 90 ms 3840 KiB
line_06 AC 63 ms 3812 KiB
line_07 AC 86 ms 3748 KiB
line_08 AC 44 ms 3680 KiB
line_09 AC 85 ms 3796 KiB
rand_00 AC 8 ms 3676 KiB
rand_01 AC 104 ms 3636 KiB
rand_02 AC 15 ms 3568 KiB
rand_03 AC 89 ms 3684 KiB
rand_04 AC 99 ms 3708 KiB
rand_05 AC 102 ms 3592 KiB
rand_06 AC 84 ms 3700 KiB
rand_07 AC 91 ms 3624 KiB
rand_08 AC 6 ms 3604 KiB
rand_09 AC 100 ms 3688 KiB
uni_00 AC 34 ms 3664 KiB
uni_01 AC 44 ms 3684 KiB
uni_02 AC 33 ms 3688 KiB
uni_03 AC 50 ms 3628 KiB
uni_04 AC 41 ms 3688 KiB
uni_05 AC 45 ms 3684 KiB
uni_06 AC 38 ms 3700 KiB
uni_07 AC 45 ms 3648 KiB
uni_08 AC 29 ms 3680 KiB
uni_09 AC 46 ms 3584 KiB