Submission #198121

#	Time	Username	Problem	Language	Result	Execution time	Memory
198121		model_code	Magic Tree (CEOI19_magictree)	C++17	100 / 100	457 ms	43740 KiB

magictree

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

#define int long long

struct node
{
    bool fruit = false;
    int day,where,weight;
    vector<int> children;
    set<pair<int,int> > harvest;
};

vector<node> tree;

int depth(int v)
{
    int ans = 0;
    for(int c : tree[v].children)
        ans = max(ans,depth(c)+1);
    return ans;
}

// merge solutions in tree[from] and tree[in]
// merge from smaller set into larger
// return index of smaller set
int join_sol(int in,int from)
{
    if(tree[from].harvest.size() > tree[in].harvest.size())
        swap(in,from);

    for(auto it = tree[from].harvest.begin(); it!=tree[from].harvest.end();it++)
    {
        int day = it->first, add = it->second;
        auto inptr = tree[in].harvest.lower_bound({day,-1});
        if(inptr == tree[in].harvest.end() || inptr->first != day)
        {
            tree[in].harvest.insert({day,add});
        }
        else //(inptr->first == day)
        {
            pair<int,int> tmp = {inptr->first, inptr->second};
            tmp.second += add;
            tree[in].harvest.erase(inptr);
            tree[in].harvest.insert(tmp);
        }
    }
    return in;
}

void solve(int v)
{

    tree[v].where = v;
    tree[v].harvest.insert({-1,0});

    for(int c : tree[v].children)
    {
        solve(c);
        tree[v].where = join_sol(tree[v].where,tree[c].where);
    }

    int w = tree[v].where;

    if(tree[v].fruit)
    {
        auto it = tree[w].harvest.lower_bound({tree[v].day,-1});

        if(it == tree[w].harvest.end())
            tree[w].harvest.insert({ tree[v].day, tree[v].weight });
        else if( it->first == tree[v].day)
        {
            pair<int,int> newval = {it->first,it->second+tree[v].weight};
            tree[w].harvest.erase(it);
            it = tree[w].harvest.insert(newval).first;
            
            int debt = tree[v].weight;
            while(debt)
            {
                auto rn = it;
                rn++;
                if(rn == tree[w].harvest.end()) break;
                pair<int,int> tmp = {rn->first,rn->second};
                tree[w].harvest.erase(rn);
                int take = min(debt, tmp.second);
                debt -= take;
                tmp.second -= take;
                if(tmp.second)
                    tree[w].harvest.insert(tmp);
            }
        }
        else
        {
            it = tree[w].harvest.insert({tree[v].day, tree[v].weight}).first;
            int debt = tree[v].weight;
            while(debt)
            {
                auto rn = it;
                rn++;
                if(rn == tree[w].harvest.end()) break;
                pair<int,int> tmp = {rn->first,rn->second};
                tree[w].harvest.erase(rn);
                int take = min(debt, tmp.second);
                debt -= take;
                tmp.second -= take;
                if(tmp.second)
                    tree[w].harvest.insert(tmp);
            }
        }
    }

}

main()
{
    int n,m,k;
    cin >> n >> m >> k;

    tree.resize(n);

    for(int i=1;i<n;++i)
    {
        int parent;
        cin >> parent;
        parent--;
        tree[parent].children.push_back(i);
    }

    for(int i=0;i<m;++i)
    {
        int pos;
        cin >> pos;
        pos--;
        tree[pos].fruit = true;
        cin >> tree[pos].day >> tree[pos].weight;
    }

    solve(0);
    int ans = 0;
    for(auto it = tree[ tree[0].where ].harvest.begin(); it != tree[ tree[0].where ].harvest.end(); it++)
        ans += it->second;
    cout << ans << "\n";

    if(VERBOSE)
    {
        cerr <<  "depth " << depth(0) << "\n";
    }
}

Compilation message (stderr)

magictree.cpp:115:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 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