oj.uz

Submission #480034

# Submission time Handle Problem Language Result Execution time Memory
480034 2021-10-14T12:29:24 Z rainboy Džumbus (COCI19_dzumbus) C
110 / 110
 71 ms 13620 KB 
#include <stdio.h>
#include <stdlib.h>

#define N	1000
#define INF	0x3f3f3f3f3f3f3f3fLL

long long min(long long a, long long b) { return a < b ? a : b; }

int *ej[N], eo[N];

void append(int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int aa[N], sz[N]; long long dp[N][N + 1][3];

void dfs(int p, int i) {
	int o, s, s_;

	sz[i] = 1;
	dp[i][0][0] = 0, dp[i][0][1] = aa[i], dp[i][0][2] = INF;
	dp[i][1][0] = INF, dp[i][1][1] = INF, dp[i][1][2] = INF;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p) {
			dfs(i, j);
			for (s = sz[i] + 1; s <= sz[i] + sz[j]; s++)
				dp[i][s][0] = dp[i][s][1] = dp[i][s][2] = INF;
			for (s = sz[i]; s >= 0; s--) {
				long long x0 = dp[i][s][0], x1 = dp[i][s][1], x2 = dp[i][s][2];

				dp[i][s][0] = INF, dp[i][s][1] = INF, dp[i][s][2] = INF;
				for (s_ = 0; s_ <= sz[j]; s_++) {
					long long y0 = dp[j][s_][0], y1 = dp[j][s_][1], y2 = dp[j][s_][2];

					dp[i][s + s_][0] = min(dp[i][s + s_][0], x0 + min(min(y0, y1), y2));
					dp[i][s + s_][1] = min(dp[i][s + s_][1], x1 + y0);
					dp[i][s + s_][2] = min(dp[i][s + s_][2], min(x2 + y2, x2 + y0));
					if (s + s_ + 1 <= sz[i] + sz[j])
						dp[i][s + s_ + 1][2] = min(dp[i][s + s_ + 1][2], min(x2 + y1, x1 + y2));
					if (s + s_ + 2 <= sz[i] + sz[j])
						dp[i][s + s_ + 2][2] = min(dp[i][s + s_ + 2][2], x1 + y1);
				}
			}
			sz[i] += sz[j];
		}
	}
}

int main() {
	static long long dq[N + 1];
	int n, m, q, h, i, j, s, s_, s1;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++) {
		scanf("%d", &aa[i]);
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	}
	for (h = 0; h < m; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		append(i, j), append(j, i);
	}
	dq[0] = 0, s1 = 0;
	for (i = 0; i < n; i++)
		if (sz[i] == 0) {
			dfs(-1, i);
			for (s = s1 + 1; s <= s1 + sz[i]; s++)
				dq[s] = INF;
			for (s = s1; s >= 0; s--) {
				long long x = dq[s];

				dq[s] = INF;
				for (s_ = 0; s_ <= sz[i]; s_++)
					dq[s + s_] = min(dq[s + s_], x + min(min(dp[i][s_][0], dp[i][s_][1]), dp[i][s_][2]));
			}
			s1 += sz[i];
		}
	for (s = n - 1; s >= 0; s--)
		dq[s] = min(dq[s], dq[s + 1]);
	scanf("%d", &q);
	while (q--) {
		long long x;
		int lower, upper;

		scanf("%lld", &x);
		lower = 0, upper = n + 1;
		while (upper - lower > 1) {
			s = (lower + upper) / 2;
			if (dq[s] <= x)
				lower = s;
			else
				upper = s;
		}
		printf("%d\n", lower);
	}
	return 0;
}

Compilation message

dzumbus.c: In function 'append':
dzumbus.c:14:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   14 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
dzumbus.c: In function 'main':
dzumbus.c:59:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
dzumbus.c:61:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
dzumbus.c:65:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~
dzumbus.c:85:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
dzumbus.c:90:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |   scanf("%lld", &x);
      |   ^~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10700 KB Output is correct
2 Correct 16 ms 12104 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10700 KB Output is correct
2 Correct 16 ms 12104 KB Output is correct
3 Correct 71 ms 13620 KB Output is correct
4 Correct 71 ms 11540 KB Output is correct
5 Correct 67 ms 10692 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 1476 KB Output is correct
2 Correct 56 ms 1292 KB Output is correct
3 Correct 56 ms 3012 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10700 KB Output is correct
2 Correct 16 ms 12104 KB Output is correct
3 Correct 71 ms 13620 KB Output is correct
4 Correct 71 ms 11540 KB Output is correct
5 Correct 67 ms 10692 KB Output is correct
6 Correct 67 ms 1476 KB Output is correct
7 Correct 56 ms 1292 KB Output is correct
8 Correct 56 ms 3012 KB Output is correct
9 Correct 59 ms 6772 KB Output is correct
10 Correct 63 ms 7212 KB Output is correct
11 Correct 71 ms 6852 KB Output is correct