Submission #477384

#	Time	Username	Problem	Language	Result	Execution time	Memory
477384		Ozy	Magic Tree (CEOI19_magictree)	C++17	100 / 100	161 ms	38296 KiB

magictree

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 100000
#define dia first
#define w second

lli n,m,lim,a,b,c,acarreo,jugo;
vector<lli> hijos[MAX+2];
pair<lli,lli> frutas[MAX+2];
set<pair<lli,lli> > subida[MAX+2];
set<pair<lli,lli> >::iterator act,it,pas;

void DFS(lli pos) {

    for (auto h : hijos[pos]) {
        DFS(h);

        if (subida[pos].size() < subida[h].size()) swap(subida[pos], subida[h]);

        act = subida[h].begin();
        while (act != subida[h].end()) {
            a = (*act).dia;
            b = (*act).w;
            act++;

            it = subida[pos].lower_bound({a,0});
            if ((*it).dia == a) {
                b += (*it).w;
                subida[pos].erase(it);
                subida[pos].insert({a,b});
            }
            else subida[pos].insert({a,b});
        }
    }

    if (frutas[pos].dia != 0) {

            lli sum = 0;
            it = subida[pos].lower_bound({frutas[pos].dia,0});

            if (it == subida[pos].end()) subida[pos].insert({frutas[pos].dia, frutas[pos].w});
            else {

                if ((*it).dia == frutas[pos].dia) {
                    jugo = (*it).w;
                    it = subida[pos].erase(it);
                }
                else jugo = 0;

                subida[pos].insert({frutas[pos].dia, frutas[pos].w + jugo});

                acarreo = 0;
                while (it != subida[pos].end() && (*it).w+acarreo <= frutas[pos].w) {
                    acarreo += (*it).w;
                    it = subida[pos].erase(it);
                }

                if (it != subida[pos].end()) {
                    a = (*it).dia;
                    b = (*it).w;
                    subida[pos].erase(it);
                    b -= (frutas[pos].w - acarreo);

                    subida[pos].insert({a,b});
                }

            }

    }

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> lim;
    rep(i,2,n) {
        cin >> a;
        hijos[a].push_back(i);
    }
    rep(i,1,m) {
        cin >> a >> b >> c;
        frutas[a] = {b,c};
    }

    DFS(1);

    it = subida[1].begin();
    a = 0;

    while (it != subida[1].end()) {
        a += (*it).w;
        it++;
    }
    cout << a << "\n";
}

Compilation message (stderr)

magictree.cpp: In function 'void DFS(long long int)':
magictree.cpp:45:17: warning: unused variable 'sum' [-Wunused-variable]
   45 |             lli sum = 0;
      |                 ^~~

• 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