oj.uz

답안 #722232

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
722232 2023-04-11T15:25:56 Z 600Mihnea Worst Reporter 4 (JOI21_worst_reporter4) C++17
0 / 100
 2000 ms 5588 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 += 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -