Submission #1320409

#TimeUsernameProblemLanguageResultExecution timeMemory
1320409trainingdnnsMagic Tree (CEOI19_magictree)C++20
0 / 100
1 ms332 KiB
#include <bits/stdc++.h>
using namespace std;

// Let dp[i] be the {maximum answer, min day to obtain that answer} for a particular node i.
// Initially for each leaf node, the answer is {0,0} if it does not have a fruit, else whatever the value of fruit it has.
// Then, to calc the answer for a node i,
//     Sort the values of the dp for all it's children according to day.
//     Iterate through each child, and if the day is less than or equal to the parent's day, accumulate it to the parent node's magic, storing it in a var max_magic
//     The answer for that node is max(max_magic, sum of dp of all children)
//     Remember to update the day, and if there are many options, choose the earliest day
using ll=long long;


int main() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ll n,m,k;
    cin>>n>>m>>k;
    struct Fruit {
        ll vertex, day, weight;
    };
    vector<vector<ll>> adj(n);
    vector<ll> parent(n,0);
    parent[0]=0;
    for(ll i=1; i<n; i++) {
        ll par;
        cin>>par;
        par--;
        adj[par].push_back(i);
        adj[i].push_back(par);
        parent[i]=par;
    }
    vector<Fruit> fruits(m);
    for(ll i=0; i<m; i++) {
        cin>>fruits[i].vertex>>fruits[i].day>>fruits[i].weight;
    }
    vector<pair<ll, ll>> fruit(n, {0, 0});
    for(auto it: fruits) {
        fruit[it.vertex-1] = {it.day, it.weight};
    }
    vector<pair<ll, long long>> dp(n, {0,0});
    vector<ll> childCnt(n,0);
    for(ll v=0; v<n; ++v){
        childCnt[v] = (ll)adj[v].size() - (v==0 ? 0 : 1);
    }

    vector<bool> visited(n, false);
    set<ll> q;
    for (ll i = 1; i < n; ++i) {
        if (childCnt[i] == 0) {
            dp[i] = { fruit[i].first , fruit[i].second };
            visited[i] = true;
            ll p = parent[i];
            if (p != i) {
                --childCnt[p];
                if (childCnt[p] == 0) q.insert(p);
            }
        }
    }
    while(!q.empty()) {
        ll cur = *q.begin();
        q.erase(q.begin());
        vector<pair<ll, long long>> children;
        for(ll nb : adj[cur]) {
            if(visited[nb]) children.push_back(dp[nb]);
        }
        if(fruit[cur].first==0 && fruit[cur].second==0) {
            long long sum = 0;
            ll max_day = 0;
            for(auto &ch : children){
                sum += ch.second;
                max_day = max(max_day, ch.first);
            }
            dp[cur] = { max_day , sum };
        } else {
            sort(children.begin(), children.end(),
                 [](const pair<ll,long long>& a,
                    const pair<ll,long long>& b){ return a.first < b.first; });

            long long max_magic = fruit[cur].second;
            long long sum = 0;
            for(auto &ch : children){
                if(ch.first <= fruit[cur].first) 
                    max_magic += ch.second;
                sum += ch.second;
            }
            ll end_day = 0;
            if(!children.empty()) end_day = children.back().first; 
            if(max_magic > sum){
                dp[cur] = { max(end_day, fruit[cur].first) , max_magic };
            } else if(sum > max_magic){
                ll max_child_day = 0;
                for(auto &ch : children) max_child_day = max(max_child_day, ch.first);
                dp[cur] = { max_child_day , sum };
            } else {
                dp[cur] = { min(end_day, fruit[cur].first) , sum };
            }
        }
        visited[cur] = true;
        ll p = parent[cur];
        if(p != cur){
            childCnt[p]--;
            if(childCnt[p]==0) q.insert(p);
        }
    }
    cout << dp[0].second << endl;
}

Compilation message (stderr)

magictree.cpp: In function 'int main()':
magictree.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...