oj.uz

Submission #943531

# Submission time Handle Problem Language Result Execution time Memory
943531 2024-03-11T14:55:08 Z thangdz2k7 Arboras (RMI20_arboras) C++17
24 / 100
 304 ms 19388 KB 
#include <bits/stdc++.h>
#define x first
#define u second
#define ll long long
#define ii pair <ll, int>

using namespace std;

const int N = 1e5 + 5;
const int mod = 1e9 + 7;

ll sumDep, sumMax, sumSec;
int n, q;
int par[N], cntDep[N], top[N];
int tin[N], tout[N], order[N], timer;
ll dep[N];
vector<int> G[N];

int getSurroundChild(int u, int v) {
	int lo = 0, hi = int(G[u].size()) - 1;
	while (lo < hi) {
		int md = (lo + hi + 1) >> 1;
		if (tin[v] < tin[G[u][md]]) hi = md - 1;
		else lo = md;
	}
	return G[u][lo];
}

ii st[N << 2];
ll lz[N << 2];

void build(int rt, int lo, int hi) {
	if (lo == hi) return st[rt] = ii(dep[order[lo]], order[lo]), lz[rt] = 0, void(0);
	int md = (lo + hi) >> 1, lc = rt << 1, rc = lc | 1;
	build(lc, lo, md), build(rc, md + 1, hi);
	st[rt] = max(st[lc], st[rc]), lz[rt] = 0;
}

void modify(int l, int r, ll x, int rt, int lo, int hi) {
	if (hi < l || r < lo) return;
	if (l <= lo && hi <= r) return st[rt].x += x, lz[rt] += x, void(0);
	int md = (lo + hi) >> 1, lc = rt << 1, rc = lc | 1;
	modify(l, r, x, lc, lo, md);
	modify(l, r, x, rc, md + 1, hi);
	st[rt] = max(st[lc], st[rc]), st[rt].x += lz[rt];
}

ii getST(int l, int r, int rt, int lo, int hi) {
	if (hi < l || r < lo) return ii(0, 0);
	if (l <= lo && hi <= r) return st[rt];
	int md = (lo + hi) >> 1, lc = rt << 1, rc = lc | 1;
	auto ver = max(getST(l, r, lc, lo, md), getST(l, r, rc, md + 1, hi));
	ver.x += lz[rt];
	return ver;
}

ii getMaxDep(int u) {
	return getST(tin[u], tout[u], 1, 1, n);
}

ii getSecDep(int u) {
	int mx = getMaxDep(u).u;
	if ((int) G[u].size() <= 1) return getST(tin[u], tin[u], 1, 1, n);
	int v = getSurroundChild(u, mx);
	return max(getST(tin[u], tin[v] - 1, 1, 1, n), getST(tout[v] + 1, tout[u], 1, 1, n));
}

int high[N], mxhigh = 0;

void dfs(int u) {
	tin[u] = ++timer;
	order[tin[u]] = u;
	for (int v : G[u]) {
		cntDep[v] = cntDep[u] + 1;
		dep[v] += dep[u];
		high[v] = high[u] + 1;
		mxhigh = max(mxhigh, high[v]);
		dfs(v);
	}
	tout[u] = timer;
}

void solve(){
    cin >> n;
	for (int u = 2; u <= n; ++u) {
		cin >> par[u];
		++par[u];
		G[par[u]].push_back(u);
	}
	dep[1] = 1;
	bool ck = true;
	for (int u = 2; u <= n; ++u) {
		cin >> dep[u];
		if (dep[u] != 1e9) ck = false;
	}

	high[1] = 1;
	dfs(1);
	build(1, 1, n);

	sumDep = 0, sumMax = 0, sumSec = 0;
	for (int u = 1; u <= n; ++u) top[u] = u;
	for (int u = 1; u <= n; ++u) {
		sumDep += dep[u];
		sumMax += dep[getMaxDep(u).u];
		sumSec += dep[getSecDep(u).u];

		int mx = getMaxDep(u).u;
		if (cntDep[top[mx]] > cntDep[u]) top[mx] = u;
	}
	cout << (sumMax + sumSec - 2 * sumDep) % mod << '\n';

	cin >> q;
	while (q --) {
		int u; ll x;
		cin >> u >> x;
		++u;

		sumDep += (tout[u] - tin[u] + 1) * x;
		sumMax += (tout[u] - tin[u] + 1) * x;
		sumSec += (tout[u] - tin[u] + 1) * x;

		ii mx = getST(tin[u], tout[u], 1, 1, n);
		mx.x += x;
		sumMax += (cntDep[u] - cntDep[top[mx.u]]) * x;

		while (true) {
			int curTop = top[mx.u];
			if (curTop == 1) break;
			int p = par[curTop];
			ii ve = getMaxDep(p);
			if (ve > mx) {
				ii tmp = getSecDep(p);
				if (tmp < mx) sumSec += mx.x - tmp.x;
				break;
			} else {
				sumSec += ve.x - getSecDep(p).x;

				int newTop = top[ve.u];
				sumMax += (cntDep[curTop] - cntDep[newTop]) * (mx.x - ve.x);
				top[ve.u] = getSurroundChild(p, ve.u);
				top[mx.u] = newTop;
			}
		}
		if ((n <= 1e3 && q <= 1e3) || mxhigh <= 100 || ck) cout << (sumMax + sumSec - 2 * sumDep) % mod << '\n';
		modify(tin[u], tout[u], x, 1, 1, n);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	solve();

	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct
3 Correct 3 ms 8672 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 18860 KB Output is correct
2 Correct 164 ms 18128 KB Output is correct
3 Correct 205 ms 18260 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 249 ms 19388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct
3 Correct 3 ms 8672 KB Output is correct
4 Correct 304 ms 18860 KB Output is correct
5 Correct 164 ms 18128 KB Output is correct
6 Correct 205 ms 18260 KB Output is correct
7 Incorrect 249 ms 19388 KB Output isn't correct
8 Halted 0 ms 0 KB -