Submission #828355

#	Time	Username	Problem	Language	Result	Execution time	Memory
828355		rainboy	Arboras (RMI20_arboras)	C11	24 / 100	5074 ms	6728 KiB

arboras

#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 (stderr)

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 / 11
• Subtask 2: 13 / 13
• Subtask 3: 0 / 31
• Subtask 4: 0 / 45