제출 #834248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
834248		bane	Magic Tree (CEOI19_magictree)	C++17	0 / 100	649 ms	1048576 KiB

magictree

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
#include <stack>
#include <iomanip>
using namespace std;
#define int long long
#define endl '\n'
vector<vector<int>>adj(100'001);
vector<pair<int,int>>fruits[100'001];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;


    for (int i = 0; i < n - 1; i++){
        int x; cin >> x; --x;
        adj[x].push_back(i+1);
        adj[i+1].push_back(x);
    }
    for (int i = 0; i < m; i++){
        int a,b,c;
        cin >> a >> b >> c;
        --a;
        fruits[a].push_back({b,c});
    }

    map<int,long long>dp[100'001];
    function<void(int,int)>dfs = [&](int u, int p){
        for(int& x : adj[u]){
            if (x == p)continue;
            dfs(x,u);
            if (dp[x].size() > dp[u].size())swap(x,u);
            for (auto j : dp[x]){
                dp[u][j.first] += j.second;
            }
            dp[x].clear();
        }

        //take this one
        if (fruits[u].size() > 0){
            long long res = fruits[u][0].second;
            while(res > 0){
                auto it = dp[u].upper_bound(fruits[u][0].first);
                if (it == dp[u].end()){
                    break;
                }
                if (it->second <= res){
                    res -= it->second;
                    dp[u].erase(it);
                }else{
                    it->second -= res;
                    break;
                }
            }
            dp[u][fruits[u][0].first] += fruits[u][0].second;
        }
    };
    dfs(0,0);
    long long ans = 0;
    for (auto j : dp[0])ans += j.second;
    cout << ans << endl;
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 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