제출 #1320363

#제출 시각아이디문제언어결과실행 시간메모리
1320363trainingdnnsMagic 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



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

    vector<bool> visited(n, false);
    set<int> q;
    for(int i=1; i<n; i++) {
        if(childCnt[i]==0) {          
            dp[i] = { fruit[i].first , (long long)fruit[i].second };
            visited[i] = true;
            q.insert(parent[i]);            
        }
    }
    while(!q.empty()) {
        int cur = *q.begin();
        q.erase(q.begin());
        vector<pair<int, long long>> children;
        for(int nb : adj[cur]) {
            if(visited[nb]) children.push_back(dp[nb]);
        }
        if(fruit[cur].first==0 && fruit[cur].second==0) {
            long long sum = 0;
            int 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<int,long long>& a,
                    const pair<int,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;
            }
            int 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){
                int 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;
        int p = parent[cur];
        if(p != cur){
            childCnt[p]--;
            if(childCnt[p]==0) q.insert(p);
        }
    }
    cout << dp[0].second << endl;
}

컴파일 시 표준 에러 (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...