Submission #1361295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1361295		eyadooz	Magic Tree (CEOI19_magictree)	C++20	100 / 100	80 ms	49868 KiB

magictree

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define endl '\n'
#define int long long

int w[200005], D[200005];
vector<int> adj[200005];
map<int, int> s[200005];
map<int, int> *dfs(int x, int p=-1) 
{
    map<int, int> *big=new map<int, int>();

    for(auto i : adj[x]) 
    {
        if(i==p) continue;
        map<int, int> *it=dfs(i, x);
        if(sz(*it)>sz(*big)) swap(*it, *big); 
        for(auto f:*it) (*big)[f.first]+=f.second;
    }
    if(D[x]!=-1) 
    {
        (*big)[D[x]]+=w[x];
        int cur=w[x];
        auto it=big->find(D[x]);
        while(cur>0) 
        {
            auto nxt=next(it);
            if(next(it)==big->end()) break;
            if(cur>=nxt->second)
            {
                cur-=nxt->second;
                big->erase(nxt);
            }
            else 
            {
                nxt->second-=cur;
                cur=0;
            }
        }
    }
    return big;
}
main()
{
    cin.tie(0) -> sync_with_stdio(0);

    int n, m, k;
    cin >> n >> m >> k;

    for(int i = 2;i <= n;i++) 
    {
        int x;
        cin >> x;
        adj[i].pb(x);
        adj[x].pb(i);
    }
    for(int i = 0;i <= n;i++) D[i]=w[i]=-1;
    for(int i = 0;i < m;i++) 
    {
        int v, d, j;
        cin >> v >> d >> j;
        D[v]=d;
        w[v]=j;
    }

    int ans=0;
    for(auto[i, w]:*dfs(1)) ans+=w;
    cout << ans;
} 

Compilation message (stderr)

magictree.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main()
      | ^~~~

• 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