Submission #722232

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
722232	2023-04-11T15:25:56 Z	600Mihnea	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	0 / 100	2000 ms	5588 KB

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];
ll get(int a) {
	ll sol = c[a];
	for (auto& b : g[a]) {
		sol += get(b);
	}
	sol = min(sol, dp[a]);
	return sol;
}
void compute(int a) {
	dp[a] = 0;
	for (auto& b : g[a]) {
		dp[a] += get(b);
	}
	dp2[a] = get(a);
	while (a) {
		dp2[a] = get(a);
		a = par[a];
	}
}
void build1(int a) {
	dp2[a] = c[a];
	for (auto& b : g[a]) {
		dep[b] = 1 + dep[a];
		build1(b);
		dp2[a] += 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);
		for (int i = 1; i <= n; i++) {
			break;
			assert(get(i) == dp2[i]);
		}
	}
	cout << get(1) << "\n";
	return 0;
}

Subtask #1

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4948 KB	Output is correct
2	Correct	4 ms	4948 KB	Output is correct
3	Correct	3 ms	4948 KB	Output is correct
4	Correct	3 ms	4948 KB	Output is correct
5	Correct	778 ms	5324 KB	Output is correct
6	Correct	1045 ms	5308 KB	Output is correct
7	Correct	609 ms	5296 KB	Output is correct
8	Correct	459 ms	5292 KB	Output is correct
9	Correct	409 ms	5296 KB	Output is correct
10	Correct	555 ms	5292 KB	Output is correct
11	Correct	567 ms	5300 KB	Output is correct
12	Execution timed out	2068 ms	5588 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-

Subtask #2

0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4948 KB	Output is correct
2	Correct	4 ms	4948 KB	Output is correct
3	Correct	3 ms	4948 KB	Output is correct
4	Correct	3 ms	4948 KB	Output is correct
5	Correct	778 ms	5324 KB	Output is correct
6	Correct	1045 ms	5308 KB	Output is correct
7	Correct	609 ms	5296 KB	Output is correct
8	Correct	459 ms	5292 KB	Output is correct
9	Correct	409 ms	5296 KB	Output is correct
10	Correct	555 ms	5292 KB	Output is correct
11	Correct	567 ms	5300 KB	Output is correct
12	Execution timed out	2068 ms	5588 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-

Subtask #3

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4948 KB	Output is correct
2	Correct	4 ms	4948 KB	Output is correct
3	Correct	3 ms	4948 KB	Output is correct
4	Correct	3 ms	4948 KB	Output is correct
5	Correct	778 ms	5324 KB	Output is correct
6	Correct	1045 ms	5308 KB	Output is correct
7	Correct	609 ms	5296 KB	Output is correct
8	Correct	459 ms	5292 KB	Output is correct
9	Correct	409 ms	5296 KB	Output is correct
10	Correct	555 ms	5292 KB	Output is correct
11	Correct	567 ms	5300 KB	Output is correct
12	Execution timed out	2068 ms	5588 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-