oj.uz

Submission #205418

# Submission time Handle Problem Language Result Execution time Memory
205418 2020-02-28T22:14:33 Z luciocf Džumbus (COCI19_dzumbus) C++14
110 / 110
 100 ms 19320 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e3+10;
const ll inf = 1e18+10;

int n;
int a[maxn];

int sz[maxn];

int pai[maxn], peso[maxn];

ll dp[maxn][maxn][2];
ll mn[maxn];

vector<int> grafo[maxn];

void init(void)
{
	for (int i = 1; i <= n; i++)
		pai[i] = i, peso[i] = 1;
}

int Find(int x)
{
	if (pai[x] == x) return x;
	return pai[x] = Find(pai[x]);
}

void Join(int x, int y)
{
	x = Find(x), y = Find(y);
	if (x == y) return;

	if (peso[x] < peso[y]) swap(x, y);

	pai[y] = x, peso[x] += peso[y];
}

void dfs(int u, int p)
{
	dp[u][0][1] = inf;
	for (int i = 1; i <= n; i++)
		dp[u][i][0] = dp[u][i][1] = inf;

	sz[u] = 1;

	for (auto v: grafo[u])
	{
		if (v == p) continue;

		dfs(v, u);
		sz[u] += sz[v];

		for (int i = sz[u]; i >= 1; i--)
		{
			for (int j = min(i, sz[v]); j >= 1 && i-j <= sz[u]-sz[v]; j--)
			{
				ll caso1 = (i-j >= 1 ? dp[u][i-j-1][0] + 1ll*a[u] + dp[v][j][1] : inf);
				ll caso2 = (i-j >= 1 ? dp[u][i-j-1][0] + 1ll*a[u] + dp[v][j-1][0] + 1ll*a[v] : inf);
				ll caso3 = dp[u][i-j][1] + dp[v][j][0];
				ll caso4 = dp[u][i-j][1] + dp[v][j][1];
				ll caso5 = dp[u][i-j][1] + dp[v][j-1][0] + 1ll*a[v];

				dp[u][i][1] = min({dp[u][i][1], caso1, caso2, caso3, caso4, caso5});
			}
		}

		for (int i = sz[u]; i >= 1; i--)
			for (int j = min(i, sz[v]); j >= 1 && i-j <= sz[u]-sz[v]; j--)
				dp[u][i][0] = min(dp[u][i][0], dp[u][i-j][0] + min(dp[v][j][0], dp[v][j][1]));

	}
}

int main(void)
{
	int m;
	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);

	init();

	for (int i = 1; i <= m; i++)
	{
		int u, v;
		scanf("%d %d", &u, &v);

		grafo[u].push_back(v);
		grafo[v].push_back(u);

		Join(u, v);
	}

	a[0] = 1e9+10;
	for (int i = 1; i <= n; i++)
		if (Find(i) == i)
			grafo[0].push_back(i);

	dfs(0, 0);

	mn[n] = dp[0][n][0];
	for (int i = n-1; i >= 1; i--)
		mn[i] = min(mn[i+1], dp[0][i][0]);

	int q;
	scanf("%d", &q);

	while (q--)
	{
		int S;
		scanf("%d", &S);

		int ini = 0, fim = n, ans = 0;

		while (ini <= fim)
		{
			int mid = (ini+fim)>>1;

			if (mn[mid] <= S) ans = mid, ini = mid+1;
			else fim = mid-1;
		}

		printf("%d\n", ans);
	}
}

Compilation message

dzumbus.cpp: In function 'int main()':
dzumbus.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
dzumbus.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:113:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
dzumbus.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &S);
   ~~~~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16680 KB Output is correct
2 Correct 29 ms 16376 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16680 KB Output is correct
2 Correct 29 ms 16376 KB Output is correct
3 Correct 84 ms 18552 KB Output is correct
4 Correct 95 ms 19320 KB Output is correct
5 Correct 100 ms 18936 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 1784 KB Output is correct
2 Correct 60 ms 1528 KB Output is correct
3 Correct 62 ms 1300 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16680 KB Output is correct
2 Correct 29 ms 16376 KB Output is correct
3 Correct 84 ms 18552 KB Output is correct
4 Correct 95 ms 19320 KB Output is correct
5 Correct 100 ms 18936 KB Output is correct
6 Correct 60 ms 1784 KB Output is correct
7 Correct 60 ms 1528 KB Output is correct
8 Correct 62 ms 1300 KB Output is correct
9 Correct 86 ms 18352 KB Output is correct
10 Correct 89 ms 18936 KB Output is correct
11 Correct 84 ms 18680 KB Output is correct