oj.uz

Submission #875155

# Submission time Handle Problem Language Result Execution time Memory
875155 2023-11-18T17:51:07 Z MinaRagy06 Arboras (RMI20_arboras) C++17
24 / 100
 5000 ms 7260 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int mod = 1e9 + 7;
struct mint {
	int v = 0;
	mint() {}
	mint(ll x) {
		v = x % mod;
	}
	mint& operator+=(mint b) {
		if ((v += b.v) >= mod) {
			v -= mod;
		}
		return *this;
	}
	mint& operator-=(mint b) {
		if ((v -= b.v) < 0) {
			v += mod;
		}
		return *this;
	}
	friend mint operator+(mint a, mint b) {
		return a += b;
	}
	friend mint operator-(mint a, mint b) {
		return a -= b;
	}
	friend bool operator>(mint a, mint b) {
		return a.v > b.v;
	}
	friend bool operator<(mint a, mint b) {
		return b > a;
	}
	friend ostream& operator<<(ostream &os, mint a) {
		return os << a.v;
	}
};
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n;
	cin >> n;
	int p[n]{};
	for (int i = 1; i < n; i++) {
		cin >> p[i];
	}
	ll d[n]{};
	for (int i = 1; i < n; i++) {
		cin >> d[i];
	}
	pair<ll, int> dp[n][2];
	for (int i = 0; i < n; i++) {
		dp[i][0] = dp[i][1] = {0, -1};
	}
	mint ans = 0;
	for (int i = n - 1; i > 0; i--) {
		if (dp[i][0].first + d[i] > dp[p[i]][1].first) {
			dp[p[i]][1] = {dp[i][0].first + d[i], i};
			if (dp[p[i]][1] > dp[p[i]][0]) swap(dp[p[i]][0], dp[p[i]][1]);
		}
		ans += dp[i][0].first + dp[i][1].first;
	}
	ans += dp[0][0].first + dp[0][1].first;
	cout << ans << '\n';
	int q;
	cin >> q;
	while (q--) {
		int i, v;
		cin >> i >> v;
		d[i] += v;
		mint old = 0, cur = -1;
		while (old.v != cur.v && i != 0) {
			old = cur = dp[p[i]][0].first;
			if (dp[p[i]][0].second == i) {
				swap(dp[p[i]][0], dp[p[i]][1]);
			}
			if (dp[p[i]][1].second == i || dp[i][0].first + d[i] > dp[p[i]][1].first) {
				ans -= dp[p[i]][0].first + dp[p[i]][1].first;
				dp[p[i]][1] = {dp[i][0].first + d[i], i};
				if (dp[p[i]][1] > dp[p[i]][0]) {
					swap(dp[p[i]][0], dp[p[i]][1]);
				}
				cur = dp[p[i]][0].first;
				ans += dp[p[i]][0].first + dp[p[i]][1].first;
			}
			i = p[i];
		}
		cout << ans << '\n';
	}
	return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 6992 KB Output is correct
2 Correct 42 ms 7260 KB Output is correct
3 Correct 41 ms 7256 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1357 ms 7164 KB Output is correct
2 Execution timed out 5055 ms 6624 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 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 42 ms 6992 KB Output is correct
5 Correct 42 ms 7260 KB Output is correct
6 Correct 41 ms 7256 KB Output is correct
7 Correct 1357 ms 7164 KB Output is correct
8 Execution timed out 5055 ms 6624 KB Time limit exceeded
9 Halted 0 ms 0 KB -