Submission #418049

#	Time	Username	Problem	Language	Result	Execution time	Memory
418049		gmyu	Magic Tree (CEOI19_magictree)	C++14	3 / 100	162 ms	36908 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];  /// at each node, the extra fruit you can get at time t

void dfs(int v, int p=0) {
    if(sz(adjlist[v])==0) {
        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(debug) {
        cout << v << " : before" << endl;
        for(auto x : dp[v]) cout << " " << x.ff << " - " << x.ss << endl;
    }

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

    dp[v][d[v]] += w[v];    // now deal with insertion;
    ll ps = 0LL;
    for(auto it = dp[v].lower_bound(d[v]); it != dp[v].end() && ps < w[v]; it++) ps += it->ss;
    if(ps <= w[v]) {
        dp[v][d[v]] -= w[v];
    } else {
        auto it = dp[v].lower_bound(d[v]);
        auto it2 = prev(dp[v].end());
        while(it2 != it) dp[v].erase(it2--);
        dp[v].erase(it);
    }

    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 5
3 3 10
4 4 10

*/

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