Submission #276669

#	Time	Username	Problem	Language	Result	Execution time	Memory
276669		Mercenary	Magic Tree (CEOI19_magictree)	C++14	100 / 100	157 ms	38648 KiB

magictree

#include<bits/stdc++.h>
#define taskname "A"
#define pb push_back
#define mp make_pair

using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
typedef long double ld;
const int maxn = 1e5 + 5;
int d[maxn] , w[maxn];
int n , m , k;
vector<int> adj[maxn];

map<int,ll> * dfs(int u){
    auto cur = new map<int,ll>;
    for(auto & c : adj[u]){
        auto tmp = dfs(c);
        if(tmp->size() > cur->size())swap(tmp,cur);
        for(auto val : (*tmp))(*cur)[val.first] += val.second;
    }
    if(d[u]){
        int val = w[u];
        while(true){
            auto it = cur->upper_bound(d[u]);
            if(it == cur->end())break;
            if(it->second <= val){
                val -= it->second;
                cur->erase(it);
            }else{
                (*cur)[it->first] -= val;
                break;
            }
        }
        (*cur)[d[u]] += w[u];
    }
    return cur;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    if(fopen(taskname".INP","r")){
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    cin >> n >> m >> k;
    for(int i = 2 ; i <= n ; ++i){
        int p;cin >> p;adj[p].pb(i);
    }
    for(int i = 1 ; i <= m ; ++i){
        int u;cin >> u;cin >> d[u] >> w[u];
    }
    ll ans = 0;
    auto res = dfs(1);
    for(auto c : (*res))ans += c.second;
    cout << ans << endl;
}

Compilation message (stderr)

magictree.cpp: In function 'int main()':
magictree.cpp:43:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   43 |         freopen(taskname".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   44 |         freopen(taskname".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