Submission #722245

#	Time	Username	Problem	Language	Result	Execution time	Memory
722245		600Mihnea	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	14 / 100	2074 ms	27636 KiB

worst_reporter2

#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <cassert>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <stack>
#include <chrono>
#include <cstring>
#include <numeric>
using namespace std;
typedef long long ll;
const int N = 200000 + 7;
const ll INF = (ll)1e18 + 7;
int n;
int par[N];
int h[N];
int c[N];
vector<int> g[N];
int dep[N];
ll dp[N];
ll dp2[N];
void compute(int a) {
	ll init = min(dp[a], dp2[a]);
	dp[a] = 0;
	for (auto& b : g[a]) {
		dp[a] += min(dp[b], dp2[b]);
	}
	dp2[a] = dp[a] + c[a];
	while (par[a]) {
		ll estim = dp2[par[a]] - init + min(dp[a], dp2[a]);
		init = min(dp[par[a]], dp2[par[a]]);
		dp2[par[a]] = estim;
		a = par[a];
	}
}
void build1(int a) {
	for (auto& b : g[a]) {
		dep[b] = 1 + dep[a];
		build1(b);
	}	
	dp2[a] = c[a];
	for (auto& b : g[a]) {
		dp2[a] += min(dp[b], dp2[b]);
	}
}
signed main() {
#ifdef ONPC	
	FILE* stream;
	freopen_s(&stream, "input.txt", "r", stdin);
#else
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
#endif
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> par[i] >> h[i] >> c[i];
		dp[i] = INF;
	}
	assert(par[1] == 1);
	par[1] = 0;
	for (int i = 2; i <= n; i++) {
		assert(1 <= par[i] && par[i] <= i - 1);
		g[par[i]].push_back(i);
	}
	build1(1);
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 1);
	sort(ord.begin(), ord.end(), [&](int a, int b) {
		if (h[a] != h[b]) {
			return h[a] > h[b];
		}
		return dep[a] > dep[b];
		});
	for (auto& a : ord) {
		compute(a);
	}
	cout << min(dp[1], dp2[1]) << "\n";
	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 65
• Subtask 3: 0 / 21