oj.uz

Submission #828355

# Submission time Handle Problem Language Result Execution time Memory
828355 2023-08-17T08:49:39 Z rainboy Arboras (RMI20_arboras) C
24 / 100
 5000 ms 6728 KB 
#include <stdio.h>
#include <string.h>

#define N	100000
#define MD	1000000007

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

int main() {
	static int pp[N], ww[N];
	static long long dp[N], jj1[N], jj2[N];
	int n, q, i, j, w, sum;

	scanf("%d", &n);
	for (j = 1; j < n; j++)
		scanf("%d", &pp[j]);
	for (j = 1; j < n; j++)
		scanf("%d", &ww[j]);
	memset(jj1, -1, n * sizeof *jj1);
	memset(jj2, -1, n * sizeof *jj2);
	for (j = n - 1; j > 0; j--) {
		dp[j] = (jj1[j] == -1 ? 0 : dp[jj1[j]]) + ww[j];
		i = pp[j];
		if (jj1[i] == -1 || dp[jj1[i]] < dp[j])
			jj2[i] = jj1[i], jj1[i] = j;
		else if (jj2[i] == -1 || dp[jj2[i]] < dp[j])
			jj2[i] = j;
	}
	sum = 0;
	for (i = 0; i < n; i++)
		sum = (sum + (jj1[i] == -1 ? 0 : dp[jj1[i]]) + (jj2[i] == -1 ? 0 : dp[jj2[i]])) % MD;
	scanf("%d", &q);
	printf("%d\n", sum);
	while (q--) {
		int d;

		scanf("%d%d", &j, &w);
		ww[j] += w, dp[j] += w, d = w;
		while (1) {
			if (j == 0)
				break;
			i = pp[j];
			if (jj1[i] == j) {
				sum = (sum + d) % MD;
				dp[i] = dp[j] + ww[i];
			} else if (dp[jj1[i]] < dp[j]) {
				sum = (sum + (j == jj2[i] ? d : dp[j] - dp[jj2[i]])) % MD;
				d = dp[j] - dp[jj1[i]];
				jj2[i] = jj1[i], jj1[i] = j;
				dp[i] = dp[j] + ww[i];
			} else {
				if (jj2[i] == j)
					sum = (sum + d) % MD;
				else if (dp[jj2[i]] < dp[j]) {
					sum = (sum + dp[j] - dp[jj2[i]]) % MD;
					jj2[i] = j;
				}
				break;
			}
			j = i;
		}
		if (sum < 0)
			sum += MD;
		printf("%d\n", sum);
	}
	return 0;
}

Compilation message

arboras.c: In function 'main':
arboras.c:14:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
arboras.c:16:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   scanf("%d", &pp[j]);
      |   ^~~~~~~~~~~~~~~~~~~
arboras.c:18:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   scanf("%d", &ww[j]);
      |   ^~~~~~~~~~~~~~~~~~~
arboras.c:32:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
arboras.c:37:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |   scanf("%d%d", &j, &w);
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 6396 KB Output is correct
2 Correct 42 ms 5960 KB Output is correct
3 Correct 40 ms 5936 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 6728 KB Output is correct
2 Execution timed out 5074 ms 6568 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 48 ms 6396 KB Output is correct
5 Correct 42 ms 5960 KB Output is correct
6 Correct 40 ms 5936 KB Output is correct
7 Correct 476 ms 6728 KB Output is correct
8 Execution timed out 5074 ms 6568 KB Time limit exceeded
9 Halted 0 ms 0 KB -