Submission #523070

#	Time	Username	Problem	Language	Result	Execution time	Memory
523070		Blondie	Magic Tree (CEOI19_magictree)	C++17	100 / 100	553 ms	485024 KiB

magictree

#include <bits/stdc++.h>
using namespace std;

#define sz(x) ((int)(x.size()))
#define all(x) x.begin(), x.end()

template<typename T> void pr(T a){std::cerr<<a<<std::endl;}
template<typename T, typename... Args> void pr(T a, Args... args){std::cerr<<a<<' ',pr(args...);}

using ll = long long;

const char nl = '\n';
const int MX = 1e5 + 10;

struct Node {
	int ls, rs;
	ll mx, mn, lz;
	Node(ll hi = 0, ll lo = 0) : ls(0), rs(0), mx(hi), mn(lo), lz(0) {}
};

Node st[int(15e6)];
int _nxt;

void addChild(int v) {
	if(st[v].ls) return;
// cerr << v->mx << " " << v->mn << nl;
	Node tmp(st[v].mx - st[v].lz, st[v].mn - st[v].lz);
	st[v].ls = ++_nxt;
	st[_nxt] = tmp;
	st[v].rs = ++_nxt;
	st[_nxt] = tmp;
}

void prop(int v) {
	if(!st[v].ls) return;
	ll& L = st[v].lz;
	int _ls = st[v].ls;
	int _rs = st[v].rs;
	st[_ls].lz += L;
	st[_ls].mx += L;
	st[_ls].mn += L;

	st[_rs].lz += L;
	st[_rs].mx += L;
	st[_rs].mn += L;
	L = 0;
}

void pull(int v) {
	st[v].mx = max(st[st[v].ls].mx, st[st[v].rs].mx);
	st[v].mn = min(st[st[v].ls].mn, st[st[v].rs].mn);
}

void upd(int v, int b, int e, int l, int r, ll x) {
	if(l >= r) return;
	addChild(v);
	if(b == l && e == r) {
		st[v].mx += x;
		st[v].mn += x;
		st[v].lz += x;
		return;
	}
	prop(v);
	int m = (b + e) / 2;
	upd(st[v].ls, b, m, l, min(r, m), x);
	upd(st[v].rs, m, e, max(l, m), r, x);
	pull(v);
}

void upd2(int v, int b, int e, int l, int r, ll x) {
	if(l >= r || st[v].mn >= x) return;
	addChild(v);
	if(b == l && e == r && st[v].mx <= x) {
		st[v].ls = st[v].rs = 0;
		st[v].mx = x;
		st[v].mn = x;
		st[v].lz = 0;
		return;
	}
	prop(v);
	int m = (b + e) / 2;
	upd2(st[v].ls, b, m, l, min(r, m), x);
	upd2(st[v].rs, m, e, max(l, m), r, x);
	pull(v);
}

ll qry(int v, int b, int e, int l, int r) {
	if(l >= r) return 0;
	addChild(v);
	if(b == l && e == r) {
		return st[v].mx;
	}
	prop(v);
	int m = (b + e) / 2;
	return max(qry(st[v].ls, b, m, l, min(r, m)), qry(st[v].rs, m, e, max(l, m), r));
}

vector<pair<int,ll>> leaves;
void getLeaves(int v, int b, int e) {
	if(!v) return;
	if(e - b == 1 || !st[v].ls) {
		if(!sz(leaves) || st[v].mx > leaves.back().second) {
			leaves.push_back({b, st[v].mx});
		}
		return;
	}
	prop(v);
	int m = (b + e) / 2;
	getLeaves(st[v].ls, b, m);
	getLeaves(st[v].rs, m, e);
}

vector<int> adj[MX];
int tree[MX];
int val[MX], day[MX];
int n, m, k, sz[MX];

void dfsSz(int v) {
	sz[v] = 1;
	for(int u : adj[v]) {
		dfsSz(u);
		sz[v] += sz[u];
	}
}

void dfs(int v) {
	int big = -1;
	for(int u : adj[v]) {
		dfs(u);
		if(big == -1 || sz[big] < sz[u]) {
			big = u;
		}
	}
	if(big == -1) {
		tree[v] = ++_nxt;
	} else {
		tree[v] = tree[big];
	}
	//cerr << "doing: " << v+1 << nl;
	for(int u : adj[v]) {
		if(u != big) {
			leaves.clear();
			getLeaves(tree[u], 0, k);
			ll prv = 0;
			for(int i = 0; i < sz(leaves); i++) {
				int nxt = i + 1 == sz(leaves) ? k : leaves[i + 1].first;
				auto [pos, x] = leaves[i];
//				cerr << prv << " " << x << " -> " << pos << " " << nxt << nl;
				assert(prv <= x);
				upd(tree[v], 0, k, pos, nxt, x);
				prv = x;
			}
		}
	}
	if(day[v] != -1) {
		ll me = val[v] + qry(tree[v], 0, k, 0, day[v]+1);
		upd2(tree[v], 0, k, day[v], k, me);
//		cerr << v+1 << ": " << me << nl;
	}
}

void solve() {
	cin >> n >> m >> k;
	fill_n(day, n, -1);
	for(int i = 1; i < n; i++) {
		int p;
		cin >> p; --p;
		adj[p].push_back(i);
	}
	ll should = 0;
	for(int i = 0; i < m; i++) {
		int v;
		cin >> v; --v;
		cin >> day[v] >> val[v];
		--day[v];
		should += val[v];
	}
	dfsSz(0);
	dfs(0);
	cout << st[tree[0]].mx << nl;
//	assert(tree[0]->mx <= should);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int te = 1;
//	cin >> te;
	while(te--) {
		solve();
	}
}

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 17 / 17