Submission #928294

#	Time	Username	Problem	Language	Result	Execution time	Memory
928294		vjudge1	Magic Tree (CEOI19_magictree)	C++17	20 / 100	78 ms	18348 KiB

magictree

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"

const int maxn = 1e5 + 100;
const ll INF = (ll)1e18 + 100;
const int MOD = 998244353;

int n, m, k, t;
vector<int> g[maxn];
ll d[maxn * 4];
int tin[maxn];
int tout[maxn];
int used[maxn];
ll dp[maxn];

void upd(int i, ll x, int v = 1, int tl = 1, int tr = n){
	if(tl == tr) d[v] = x;
	else{
		int mid = (tl + tr) >> 1;
		if(i <= mid) upd(i, x, v<<1, tl, mid);
		else upd(i, x, v<<1|1, mid+1, tr);
		d[v] = max(d[v<<1], d[v<<1|1]);
	}
}

ll get(int l, int r, int v = 1, int tl = 1, int tr = n){
	if(tr < l || tl > r) return 0;
	if(l <= tl && tr <= r) return d[v];
	int mid = (tl + tr) >> 1;
	return max(get(l, r, v<<1, tl, mid)
	, get(l, r, v<<1|1, mid+1, tr));
}

void calc(int v = 1){
	tin[v] = ++t;
	for(int to: g[v]){
		calc(to);
	}
	tout[v] = t;
}

pii f(tuple<int, int, int> x){
	auto [d, v, w] = x;
	return {d, -tin[v]};
}

void dfs(int v = 1){
	ll sum = 0;
	for(int to: g[v]){
		dfs(to);
		sum += dp[to];
	}
	dp[v] = max(dp[v], sum);
}

void test(){
	cin >> n >> m >> k;
	for(int i = 2; i <= n; i++){
		int p; cin >> p;
		g[p].push_back(i);
	} calc();
	vector<tuple<int, int, int>> q;
	for(int i = 1; i <= m; i++){
		int v, d, w;
		cin >> v >> d >> w;
		q.push_back({d, v, w});
		used[v] = 1;
	}
	for(int i = 1; i <= n; i++){
		if(!used[i]) q.push_back({k + 1, i, 0});
	}
	sort(q.begin(), q.end(), [](tuple<int, int, int> a, tuple<int, int, int> b){
		return f(a) < f(b);
	});
	for(auto [d, v, w]: q){
		dp[v] = w;
		for(int to: g[v]){
			dp[v] += get(tin[to], tout[to]);
		}
		upd(tin[v], dp[v]);
	}
	dfs();
	cout << dp[1];
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    // #endif
	int t; t = 1;
	while(t--) test();
}

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