Submission #1286752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286752		thieunguyenhuy	Magic Tree (CEOI19_magictree)	C++20	15 / 100	101 ms	45988 KiB

magictree

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

#define POPCOUNT(n) (__builtin_popcountll((n)))
#define CLZ(n) (__builtin_clzll((n)))
#define CTZ(n) (__builtin_ctzll((n)))
#define LOG(n) (63 - __builtin_clzll((n)))
#define BIT(n, i) (((n) >> (i)) & 1ll)
#define MASK(i) (1ll << (i))
#define FLIP(n, i) ((n) ^ (1ll << (i)))
#define ON(n, i) ((n) | MASK(i))
#define OFF(n, i) ((n) & ~MASK(i))

#define Int __int128
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long, long long>> vll;
typedef vector<pair<long long, int>> vli;
typedef vector<pair<int, long long>> vil;

template <class T1, class T2> bool maximize(T1 &x, T2 y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <class T1, class T2> bool minimize(T1 &x, T2 y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template <class T> void remove_duplicate(vector<T> &ve) {
    sort (ve.begin(), ve.end());
    ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
}

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long long random(long long l, long long r) {
    return uniform_int_distribution<long long>(l, r)(rng);
}
unsigned long long random(unsigned long long l, unsigned long long r) {
    return uniform_int_distribution<unsigned long long>(l, r)(rng);
}
template <class T> T random(T r) {
    return rng() % r;
}

const int N = 1e5 + 5;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const long long INF = 1e18;

int n, m, k;
pii a[N];
vector<int> adj[N];

struct SlopeTrick {
	map<int, ll> slope;
	ll rightSlope, value;

	SlopeTrick() {
		slope.clear();
		rightSlope = value = 0;
	}

	int size() {
		return slope.size();
	}

	bool empty() {
		return size() == 0;
	}

	void add(ll x, ll y) {
		slope[x] += y;
	}
} T[N];

void dfs(int u) {
	if (a[u] != make_pair(0, 0)) {
		T[u].slope[a[u].fi] = a[u].se;
		T[u].slope[a[u].fi + 1] = -a[u].se;
		T[u].rightSlope = 0;
		T[u].value = 0;
	}
	for (auto v : adj[u]) {
		dfs(v);
		if (T[u].size() < T[v].size()) swap(T[u], T[v]);
		if (!T[u].empty() && !T[v].empty()) {
			ll x = T[u].slope.rbegin()->fi, y = T[v].slope.rbegin()->fi;
			if (x < y) {
				T[u].value += T[u].rightSlope * (y - x);
			}
			else {
				T[v].value += T[v].rightSlope * (x - y);
			}
			T[u].rightSlope += T[v].rightSlope;
			T[u].value += T[v].value;
			// cerr << "merge " << u << ' ' << v << ' ' << T[u].value << '\n';
			for (auto &x : T[v].slope) T[u].add(x.fi, x.se);
		}
	}

	while (!T[u].empty() && T[u].rightSlope - T[u].slope.rbegin()->se > 0) {
		auto it = T[u].slope.rbegin();
		T[u].value += (T[u].rightSlope - it->se) * (it->fi - prev(it)->fi);
		T[u].rightSlope -= it->se, T[u].slope.erase(it->fi);
	}
	T[u].rightSlope = 0;

	// cerr << "value " << u << ' ' << T[u].value << ' ' << T[u].rightSlope << '\n';
	// for (auto &x : T[u].slope) cerr << x.fi << ' ' << x.se << '\n';
	// cerr << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m >> k;

    for (int i = 2; i <= n; ++i) {
    	int p; cin >> p;
    	adj[p].emplace_back(i);
    }

    for (int i = 1; i <= m; ++i) {
    	int v, d, w; cin >> v >> d >> w;
    	a[v] = make_pair(d, w);
    }

    dfs(1);
    cout << T[1].value;
    return 0;
}

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