| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 899554 | LucaIlie | Worst Reporter 4 (JOI21_worst_reporter4) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5;
int n;
int parent[MAX_N + 1], height[MAX_N + 1], cost[MAX_N + 1];
long long dp[MAX_N + 1][MAX_N + 1];
vector<int> children[MAX_N + 1];
//map<int, int> mp;
//map<int, long long> inc[MAX_N + 1];
void dfs( int u ) {
for ( int v: children[u] )
dfs( v );
/*int maxSize = 0, h = -1;
for ( int v: children[u] ) {
if ( inc[v].size() > maxSize ) {
maxSize = inc[v].size();
h = v;
}
}
/*if ( h == -1 ) {
inc[u][0] -= cost[u];
inc[u][height[u] + 1] += cost[u];
return;
}
swap( inc[u], inc[h] );
for ( int v: children[u] ) {
if ( v == h )
continue;
for ( auto x: inc[v] )
inc[u][x.first] += x.second;
inc[v].clear();
}*/
/*auto p = inc[u].begin();
long long c = 0;
while ( p != inc[u].end() && p->first <= height[u] ) {
c += p->second;
p++;
}
c -= cost[u];
/*int k = 0;
long long s = 0;
p = inc[u].begin();
while ( p != inc[u].end() && s <= c ) {
k++;
s += p->second;
p++;
}
for ( int i = 0; i < k; i++ )
inc[u].erase( inc[u].begin() );
inc[u][0] += c;
if ( p != inc[u].end() )
inc[u][p->second] -= c;*/
/*dp[u][n] = INF;
for ( int x = n - 1; x >= 0; x-- ) {
for ( int v: children[u] )
dp[u][x] += dp[v][x];
}
long long c = dp[u][height[u]] - cost[u];
for ( int x = height[u]; x >= 0; x-- )
dp[u][x] = min( dp[u][x], c );
for ( int x = 0; x < n; x++ )
printf( "%d ", dp[u][x] );
printf( "\n" );*/
}
int main() {
long long c = 0;
cin >> n;
for ( int v = 1; v <= n; v++ )
cin >> parent[v] >> height[v] >> cost[v];
for ( int v = 2; v <= n; v++ )
children[parent[v]].push_back( v );
/*for ( int v = 1; v <= n; v++ )
mp[height[v]] = 1, c += cost[v];
int val = 0;
for ( auto p: mp )
mp[p.first] = val++;
for ( int v = 1; v <= n; v++ )
height[v] = mp[height[v]];*/
dfs( 1 );
cout << c + dp[1][0] << "\n";
return 0;
}