This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5;
bool hasFruit[MAX_N + 1];
int fruitTime[MAX_N + 1], fruitWeight[MAX_N + 1];
vector<int> adj[MAX_N + 1];
map<int, long long> dif[MAX_N + 1];
long long dp[MAX_N + 1][21];
void dfs( int u ) {
int h = 0;
for ( int v: adj[u] ) {
dfs( v );
if ( h == 0 || dif[v].size() > dif[h].size() )
h = v;
}
if ( h != 0 ) {
swap( dif[u], dif[h] );
for ( int v: adj[u] ) {
if ( v == h )
continue;
for ( auto p: dif[v] )
dif[u][p.first] += p.second;
}
}
if ( hasFruit[u] ) {
auto p = dif[u].lower_bound( fruitTime[u] );
long long sum = 0;
vector<int> del;
while ( p != dif[u].end() && fruitWeight[u] > sum + p->second ) {
sum += p->second;
del.push_back( p->first );
p++;
}
for ( int t: del )
dif[u].erase( t );
dif[u][fruitTime[u]] += fruitWeight[u];
if ( p != dif[u].end() )
dif[u][p->first] -= fruitWeight[u];
}
/*printf( "%d:\n", u );
for ( auto p: dif[u] )
printf( "%d %d\n", p.first, p.second );
printf( "\n\n" );*/
for ( int d = 0; d <= 20; d++ ) {
dp[u][d] = (fruitTime[u] == d ? fruitWeight[u] : 0);
for ( int v: adj[u] )
dp[u][d] += dp[v][d];
if ( d > 0 )
dp[u][d] = max( dp[u][d], dp[u][d - 1] );
}
}
int main() {
int n, m, k;
cin >> n >> m >> k;
for ( int v = 2; v <= n; v++ ) {
int p;
cin >> p;
adj[p].push_back( v );
}
for ( int i = 0; i < m; i++ ) {
int v;
cin >> v;
hasFruit[v] = true;
cin >> fruitTime[v] >> fruitWeight[v];
}
dfs( 1 );
long long sum = 0;
for ( auto p: dif[1] )
sum += p.second;
cout << dp[1][20];
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |