Submission #583484

#	Time	Username	Problem	Language	Result	Execution time	Memory
583484		79brue	Magic Tree (CEOI19_magictree)	C++17	100 / 100	161 ms	28804 KiB

magictree

#include <bits/stdc++.h>
#ifndef TEST
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#endif

using namespace std;

typedef long long ll;

struct Fruit{
    int v, d; ll w;
    Fruit(){}
    Fruit(int v, int d, ll w): v(v), d(d), w(w){}
};

int n, m, k;
int par[100002];
vector<int> child[100002];
int state[100002];
Fruit fruit[100002];

int day[100002];
ll weight[100002];
int root[100002];

map<int, ll> mp[100002];

void renumber(){
    vector<int> dVec;
    for(int i=1; i<=m; i++) dVec.push_back(fruit[i].d);
    sort(dVec.begin(), dVec.end());
    dVec.erase(unique(dVec.begin(), dVec.end()), dVec.end());
    for(int i=1; i<=m; i++) fruit[i].d = lower_bound(dVec.begin(), dVec.end(), fruit[i].d) - dVec.begin() + 1;
    k = (int)dVec.size();
}

void update(int i, int x, ll v){ /// v만큼 더한다
    mp[i][x] += v;
}

void nextRemove(int i, int x, ll v){
    auto it = mp[i].upper_bound(x);
    while(v && it != mp[i].end()){
        pair<int, ll> tp = *it;
        ll tmp = min(tp.second, v);
        mp[i][tp.first] -= tmp;
        v -= tmp;
        if(!mp[i][tp.first]) mp[i].erase(tp.first);
        it = mp[i].upper_bound(x);
    }
}

void mergeSet(int l, int r){
    if(mp[l].size() < mp[r].size()) mp[l].swap(mp[r]);
    for(auto x: mp[r]){
        mp[l][x.first] += x.second;
    }
    mp[r].clear();
}

void dfs(int x){
    for(auto y: child[x]){
        dfs(y);
        mergeSet(x, y);
    }
    if(day[x]){
        update(x, day[x], weight[x]);
        nextRemove(x, day[x], weight[x]);
    }
}

int main(){
    scanf("%d %d %d", &n, &m, &k);
    for(int i=2; i<=n; i++){
        scanf("%d", &par[i]);
        child[par[i]].push_back(i);
    }

    for(int i=1; i<=m; i++){
        int v, d, w;
        scanf("%d %d %d", &v, &d, &w);
        fruit[i] = Fruit(v, d, w);
    }
    renumber();
    for(int i=1; i<=m; i++){
        day[fruit[i].v] = fruit[i].d;
        weight[fruit[i].v] = fruit[i].w;
    }

    dfs(1);

    ll ans = 0;
    for(auto x: mp[1]) ans += x.second;
    printf("%lld", ans);
}

Compilation message (stderr)

magictree.cpp: In function 'int main()':
magictree.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     scanf("%d %d %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         scanf("%d", &par[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
magictree.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         scanf("%d %d %d", &v, &d, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• 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