제출 #1170272

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170272		InvMOD	Magic Tree (CEOI19_magictree)	C++20	100 / 100	94 ms	34632 KiB

magictree

#include<bits/stdc++.h>

using namespace std;

#define sz(v) (int)(v).size()

template<typename T> bool ckmx(T& a, const T& b){
    if(a < b)
        return a = b, true;
    return false;
}

using ll = long long;

void solve()
{
    int n,m,k; cin >> n >> m >> k;

    vector<vector<int>> adj(n + 1, vector<int>());
    for(int i = 2; i <= n; i++){
        int p; cin >> p;
        adj[p].push_back(i);
    }

    vector<int> day(n + 1, -1), magic(n + 1);
    for(int i = 1; i <= m; i++){
        int v; cin >> v >> day[v] >> magic[v];
    }

    vector<map<int,ll>> dp(n + 1, map<int, ll>());

    function<void(int)> calc_dp = [&](int x) -> void{
        for(int v : adj[x]){
            calc_dp(v);

            if(sz(dp[x]) < sz(dp[v])) swap(dp[x], dp[v]);

            for(auto it : dp[v]){
                dp[x][it.first] += it.second;
            }
        }

        if(day[x] != -1){
            // erase some that is not optimal for our answer like Lis
            ll cur_sum = 0;
            for(auto it = dp[x].upper_bound(day[x]); it != dp[x].end(); it = dp[x].upper_bound(day[x])){
                cur_sum += it -> second;
                if(cur_sum <= magic[x]){
                    // we will erase this to choose x
                    dp[x].erase(it);
                }
                else{
                    // does not reach the last position -> we can't choose x
                    // we erased cur_sum - it.se and add magic[x]
                    cur_sum = cur_sum - (it -> second);
                    it->second += cur_sum - magic[x];
                    break;
                }
            }
            dp[x][day[x]] += magic[x];
        }

//        cout << "DP: " << x << "\n";
//        for(auto it : dp[x]){
//            cout << it.first <<" " << it.second << "\n";
//        } cout << "\n";
    };

    calc_dp(1);

    ll answer = 0;
    for(auto it : dp[1])
        answer += it.second;
    cout << answer << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    solve();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

magictree.cpp: In function 'int32_t main()':
magictree.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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