Submission #1231127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231127		damamila	Worst Reporter 4 (JOI21_worst_reporter4)	C++20	14 / 100	2095 ms	30024 KiB

worst_reporter2

#include <bits/stdc++.h>

using namespace std;

#define int long long

vector<vector<int>> g;
vector<int> cost;
vector<int> h;
vector<pair<int, int>> dp;

int dfs2(int u, int x) {
	int ans = 1e18;
	if (h[u] >= x) { //can keep root
		ans = dp[u].first;
	}
	int tmp = cost[u];
	for (int v : g[u]) {
		tmp += dfs2(v, x);
	}
	ans = min(ans, tmp);
	//~ cout << "OTHER: " << u << " "<< x << " " << ans << endl;
	return ans;
}

void dfs(int u) {
	dp[u].second += cost[u];
	for (int v : g[u]) {
		dfs(v);
		dp[u].second += min(dp[v].first, dp[v].second);
		dp[u].first += dfs2(v, h[u]);
	}
	//~ cout << u << ": " << dp[u].first << " " << dp[u].second << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);  
	int n;
	cin >> n;
	g = vector<vector<int>> (n);
	dp = vector<pair<int, int>> (n, {0, 0});
	cost = vector<int> (n);
	h = vector<int> (n);
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a >> h[i] >> cost[i];
		a--;
		if (a != i) g[a].push_back(i);
	}
	dfs(0);
	int ans = min(dp[0].first, dp[0].second);
	cout << ans << endl;
}

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