oj.uz

답안 #722218

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
722218 2023-04-11T15:15:47 Z 600Mihnea Worst Reporter 4 (JOI21_worst_reporter4) C++17
0 / 100
 6 ms 5204 KB 
#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 += dp2[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);
	int b = par[a];
	while (b && get(b) < dp2[b]) {
		dp2[b] = get(b);
		b = par[b];
	}
}
void build1(int a) {
	for (auto& b : g[a]) {
		dep[b] = 1 + dep[a];
		build1(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] = dp2[i] = INF;
	}
	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);
	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 << dp2[1] << "\n";
	return 0;
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 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 Incorrect 6 ms 5204 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 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 Incorrect 6 ms 5204 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 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 Incorrect 6 ms 5204 KB Output isn't correct
6 Halted 0 ms 0 KB -