Submission #722194

#	Time	Username	Problem	Language	Result	Execution time	Memory
722194		600Mihnea	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	14 / 100	2065 ms	34376 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];
ll sumc[N];
ll dp[N];
ll compute(int a, int dim) {
	ll sol = c[a];
	for (auto& b : g[a]) {
		sol += compute(b, dim);
	}
	if (h[a] >= dim) {
		sol = min(sol, dp[a]);
	}
	return sol;
}
void build1(int a) {
	sumc[a] = c[a];
	dp[a] = 0;
	for (auto& b : g[a]) {
		build1(b);
		sumc[a] += sumc[b];
		dp[a] += compute(b, h[a]);
	}
}
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];
	}
	assert(par[1] == 1);
	for (int i = 2; i <= n; i++) {
		assert(1 <= par[i] && par[i] <= i - 1);
		g[par[i]].push_back(i);
	}
	build1(1);
	cout << compute(1, 0) << "\n";
	return 0;
}

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