Submission #523069

#	Time	Username	Problem	Language	Result	Execution time	Memory
523069		Blondie	Magic Tree (CEOI19_magictree)	C++17	100 / 100	837 ms	596568 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 {
	Node *ls, *rs;
	ll mx, mn, lz;
	Node(ll hi = 0, ll lo = 0) : ls(NULL), rs(NULL), mx(hi), mn(lo), lz(0) {}
};

void addChild(Node* v) {
	if(v->ls) return;
// cerr << v->mx << " " << v->mn << nl;
	assert(v->mx == v->mn);
	v->ls = new Node(v->mx - v->lz, v->mn - v->lz);
	v->rs = new Node(v->mx - v->lz, v->mn - v->lz);
}

void prop(Node* v) {
	if(!v->ls) return;
	ll& L = v->lz;
	v->ls->lz += L;
	v->ls->mx += L;
	v->ls->mn += L;

	v->rs->lz += L;
	v->rs->mx += L;
	v->rs->mn += L;
	L = 0;
}

void pull(Node* v) {
	v->mx = max(v->ls->mx, v->rs->mx);
	v->mn = min(v->ls->mn, v->rs->mn);
}

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

void upd2(Node* v, int b, int e, int l, int r, ll x) {
	if(l >= r || v->mn >= x) return;
	addChild(v);
	if(b == l && e == r && v->mx <= x) {
		v->ls = v->rs = NULL;
		v->mx = x;
		v->mn = x;
		v->lz = 0;
//		pr("upd:", b+1, e, x);
		return;
	}
	prop(v);
	int m = (b + e) / 2;
	upd2(v->ls, b, m, l, min(r, m), x);
	upd2(v->rs, m, e, max(l, m), r, x);
	pull(v);
}

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

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

vector<int> adj[MX];
Node* 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] = new Node();
	} 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 << 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