oj.uz

답안 #828641

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
828641 2023-08-17T13:02:51 Z rainboy Arboras (RMI20_arboras) C
100 / 100
 111 ms 21464 KB 
#include <stdio.h>
#include <stdlib.h>

#define N	100000
#define N_	(1 << 17)	/* N_ = pow2(ceil(log2(N + 1))) */
#define MD	1000000007

long long max(long long a, long long b) { return a > b ? a : b; }

int *ej[N], eo[N], 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 dd[N], pp[N], qq[N], jj[N], jj1[N], jj2[N], ta[N], tb[N], qu[N], ww[N]; long long dp[N];

int dfs1(int p, int i, int d) {
	int o, s, k_, j_, j1, j2;

	dd[i] = d, pp[i] = p;
	s = 1, k_ = 0, j_ = -1, j1 = -1, j2 = -1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p) {
			int k = dfs1(i, j, d + 1);

			s += k;
			if (k_ < k)
				k_ = k, j_ = j;
			dp[j] += ww[j];
			if (j1 == -1 || dp[j1] < dp[j])
				j2 = j1, j1 = j;
			else if (j2 == -1 || dp[j2] < dp[j])
				j2 = j;
		}
	}
	jj[i] = j_;
	dp[i] = j1 == -1 ? 0 : dp[j1], jj1[i] = j1, jj2[i] = j2;
	return s;
}

long long st[N_ * 2], lz[N_]; int h_, n_;

void put(int i, long long x) {
	st[i] += x;
	if (i < n_)
		lz[i] += x;
}

void pus(int i) {
	if (lz[i])
		put(i << 1 | 0, lz[i]), put(i << 1 | 1, lz[i]), lz[i] = 0;
}

void pul(int i) {
	if (!lz[i])
		st[i] = max(st[i << 1 | 0], st[i << 1 | 1]);
}

void push(int i) {
	int h;

	for (h = h_; h > 0; h--)
		pus(i >> h);
}

void pull(int i) {
	while (i > 1)
		pul(i >>= 1);
}

void build() {
	static long long dd[N + 1];
	int i;

	for (i = 1; i < n; i++)
		dd[ta[i]] += ww[i], dd[tb[i]] -= ww[i];
	for (i = 1; i < n; i++)
		dd[i] += dd[i - 1];
	for (i = 0; i < n_; i++)
		st[n_ + i] = i < n ? dd[i] : 0;
	for (i = n_ - 1; i > 0; i--)
		pul(i);
}

void update(int l, int r, int x) {
	int l_ = l += n_, r_ = r += n_;

	push(l_), push(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			put(l++, x);
		if ((r & 1) == 0)
			put(r--, x);
	}
	pull(l_), pull(r_);
}

long long query(int l, int r) {
	long long x;

	push(l += n_), push(r += n_);
	x = 0;
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			x = max(x, st[l++]);
		if ((r & 1) == 0)
			x = max(x, st[r--]);
	}
	return x;
}

int st_[N_ * 2];

void pul_(int i) {
	st_[i] = st_[i << 1 | 0] && st_[i << 1 | 1];
}

void update_(int i, int x) {
	st_[i += n_] = x;
	while (i > 1)
		pul_(i >>= 1);
}

int query_(int r) {
	int l = 0;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((r & 1) == 0) {
			if (!st_[r]) {
				while (r < n_)
					r = !st_[r << 1 | 1] ? r << 1 | 1 : r << 1 | 0;
				return r - n_;
			}
			r--;
		}
	return -1;
}

void dfs2(int p, int i, int q) {
	static int time;
	int o, j_;

	qu[ta[i] = time++] = i;
	qq[i] = q;
	j_ = jj[i];
	if (j_ != -1) {
		dfs2(i, j_, q);
		update_(ta[j_], j_ == jj1[i]);
	}
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p && j != j_)
			dfs2(i, j, j);
	}
	tb[i] = time;
}

int main() {
	int q, i, j, w, sum;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (j = 1; j < n; j++) {
		scanf("%d", &pp[j]);
		append(pp[j], j);
	}
	for (j = 1; j < n; j++)
		scanf("%d", &ww[j]);
	dfs1(-1, 0, 0);
	while (1 << h_ <= n)
		h_++;
	n_ = 1 << h_;
	dfs2(-1, 0, 0);
	build();
	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 x;
		long long d, d1, d2;

		scanf("%d%d", &j, &w);
		update(ta[j], tb[j] - 1, w);
		ww[j] += w, x = w;
		while (1) {
			i = qu[query_(ta[j])];
			sum = (sum + (long long) x * (dd[j] - dd[i])) % MD;
			j = i;
			if (j == 0)
				break;
			i = pp[j];
			if (jj1[i] == j)
				sum = (sum + x) % MD;
			else {
				d = query(ta[j], tb[j] - 1);
				d1 = query(ta[jj1[i]], tb[jj1[i]] - 1);
				d2 = query(ta[jj2[i]], tb[jj2[i]] - 1);
				if (d1 < d) {
					sum = (sum + (j == jj2[i] ? x : d - d2)) % MD;
					x = d - d1;
					jj2[i] = jj1[i], jj1[i] = j;
					update_(ta[jj[i]], jj[i] == j);
				} else {
					if (jj2[i] == j)
						sum = (sum + x) % MD;
					else if (d2 < d) {
						sum = (sum + d - d2) % MD;
						jj2[i] = j;
					}
					break;
				}
			}
			j = i;
		}
		if (sum < 0)
			sum += MD;
		printf("%d\n", sum);
	}
	return 0;
}

Compilation message

arboras.c: In function 'append':
arboras.c:15:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   15 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
arboras.c: In function 'main':
arboras.c:169:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
arboras.c:173:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |   scanf("%d", &pp[j]);
      |   ^~~~~~~~~~~~~~~~~~~
arboras.c:177:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |   scanf("%d", &ww[j]);
      |   ^~~~~~~~~~~~~~~~~~~
arboras.c:187:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  187 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
arboras.c:193:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  193 |   scanf("%d%d", &j, &w);
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 111 ms 14816 KB Output is correct
2 Correct 67 ms 15692 KB Output is correct
3 Correct 83 ms 15836 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 16396 KB Output is correct
2 Correct 92 ms 21464 KB Output is correct
3 Correct 107 ms 17328 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 111 ms 14816 KB Output is correct
5 Correct 67 ms 15692 KB Output is correct
6 Correct 83 ms 15836 KB Output is correct
7 Correct 103 ms 16396 KB Output is correct
8 Correct 92 ms 21464 KB Output is correct
9 Correct 107 ms 17328 KB Output is correct
10 Correct 105 ms 18484 KB Output is correct
11 Correct 84 ms 21196 KB Output is correct
12 Correct 95 ms 17128 KB Output is correct
13 Correct 85 ms 19404 KB Output is correct
14 Correct 85 ms 20136 KB Output is correct