oj.uz

Submission #418052

# Submission time Handle Problem Language Result Execution time Memory
418052 2021-06-05T00:59:26 Z gmyu Magic Tree (CEOI19_magictree) C++14
3 / 100
 164 ms 34688 KB 
/*
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;
    if(dp[v].upper_bound(d[v]) == dp[v].end()) return;
    ll ps = 0LL;
    for(auto it = dp[v].upper_bound(d[v]); it != dp[v].end() && ps < w[v]; it++) {
        ps += it->ss;
        //cout << it->ff << " = " << it->ss << endl;
    }
    if(ps >= w[v]) {
        dp[v][d[v]] -= w[v];
    } else {
        auto it = dp[v].upper_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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7244 KB Output is correct
2 Incorrect 5 ms 7372 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 17564 KB Output is correct
2 Correct 53 ms 19436 KB Output is correct
3 Correct 164 ms 34688 KB Output is correct
4 Correct 97 ms 18116 KB Output is correct
5 Correct 139 ms 19972 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 13664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7244 KB Output is correct
2 Incorrect 5 ms 7372 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8012 KB Output is correct
2 Correct 53 ms 10384 KB Output is correct
3 Correct 38 ms 10476 KB Output is correct
4 Correct 49 ms 10436 KB Output is correct
5 Correct 14 ms 8780 KB Output is correct
6 Incorrect 37 ms 13308 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7244 KB Output is correct
2 Incorrect 5 ms 7372 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7244 KB Output is correct
2 Incorrect 5 ms 7372 KB Output isn't correct
3 Halted 0 ms 0 KB -