Submission #418706

#	Time	Username	Problem	Language	Result	Execution time	Memory
418706		gmyu	Magic Tree (CEOI19_magictree)	C++14	100 / 100	178 ms	36876 KiB

magictree

/*
ID: USACO_template
LANG: C++
PROG: 10542-005137
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>
#include <string.h>
#include <set>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define ff  first
#define ss  second
#define pb  push_back
#define sz(x)   (int)(x).size()

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 100007
#define MAXE 100007



bool debug;

int N, M, K;
vi adjlist[MAXV];
int d[MAXV], w[MAXV];
map<int, ll> dp[MAXV];
/** dp[v, t] is the max added fruit at node v at time t.
    for a fixed v, the dp[t] looks like a stair-case plot. At time t, increase by dp[t] amount
    for v, "sum up" all child nodes, using small to large merge
    the key is to deal with node v update when there is a fruit on v. Basically, we want to get the fruit as early as possible,
    any child with t < d[v], we can simply take it; for t > d[v], whatever on node v overtakes it until it can not overtake anymore
*/

void dfs(int v, int p=0) {
    if(sz(adjlist[v])==0) { // leaf
        if(d[v]!=0) dp[v][d[v]] = w[v];
        return;
    }

    for(auto x : adjlist[v]) {
        if(x == p) continue;
        dfs(x, v);

        // small to large merge, O(N log N)
        if(sz(dp[v])<sz(dp[x])) dp[v].swap(dp[x]);
        for(auto y : dp[x]) {
            if(y.ss == 0) continue;
            dp[v][y.ff] += y.ss;
        }
    }

    if(d[v]==0) return;   // no fruit here

    dp[v][d[v]] += w[v];    // now deal with insertion;
    int cur_d = d[v], cur_val = w[v];
    while(true) {
        auto it = dp[v].upper_bound(cur_d);
        if(it == dp[v].end()) break;
        if(cur_val >= it->ss) { // adder overtake this day's value
            cur_val -= it->ss;
            dp[v].erase(it);
        } else {
            it->ss -= cur_val;
            break;
        }
    }

    if(debug) {
        cout << v << " : after " << endl;
        for(auto x : dp[v]) cout << " " << x.ff << " - " << x.ss << endl;
    }

}

int main() {
    debug = false;
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N >> M >> K;
    for(int i=2; i<=N; i++) {
        int a; cin >> a;
        adjlist[a].pb(i);
    }
    for(int i=0;i<M;i++) {
        int a, b, c; cin >> a >> b >> c;
        d[a] = b; w[a] = c;
    }

    dfs(1);

    ll ans = 0LL;
    for(auto x : dp[1]) ans += x.ss;
    cout << ans << endl;

    if(debug) cout << endl << "EOL" << endl;

}

/**
6 4 10
1
2
1
4
4
3 4 5
4 7 2
5 4 1
6 9 3

4 3 3
1
2
2
2 2 50
3 3 10
4 4 10

*/

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 17 / 17