Submission #1248458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248458		Chris_Black	Magic Tree (CEOI19_magictree)	C++20	71 / 100	115 ms	36932 KiB

magictree

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")

#include <bits/stdc++.h>

#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORR(i, a, b) for(int i = a; i >= b; --i)
#define pii pair<int, int>
#define ff first
#define ss second
#define pll pair<ll, ll>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define vpl vector<pll>
#define vvpl vector<vpl>
#define vl vector<ll>
#define vvl vector<vl>
//#define x first
//#define y second


using namespace std;
const int N = 1e5 + 9, LGV = 33, LGN = 21, Mod = 1e9 + 7;
//const int Inf = 0x3f3f3f3f;
const ll Inf = LLONG_MAX / 2;
const bool test_case = false;

//ifstream fin("landscape.in");
//ofstream fout("landscape.out");
//#define cin fin
//#define cout fout

int n, m, k, d[N], f[N];
multiset<pll> mst[N];
vvi G(N);

void Dfs(int x, int p)
{
    for(auto y : G[x])
    {
        Dfs(y, x);

        if(mst[x].size() < mst[y].size())
            swap(mst[x], mst[y]);
        for(auto e : mst[y])mst[x].insert(e);
    }

    if(d[x])
    {
        multiset<pll>::iterator it = mst[x].insert({d[x], f[x]});

        ll v = f[x];
        auto nx = it; ++nx;
        while(nx != mst[x].end())
            if(v >= (*nx).ss)
            {
                v -= (*nx).ss;
                nx = mst[x].erase(nx);
            }
            else
            {
                auto aux = *nx;
                mst[x].erase(nx);
                aux.ss -= v;
                mst[x].insert(aux);
                break;
            }
    }
}


void solve()
{
    cin >> n >> m >> k;

    int p;
    FOR(i, 2, n)
    {
        cin >> p;
        G[p].pb(i);
    }

    int v;
    FOR(i, 1, m)
        cin >> v >> d[v] >> f[v];

    Dfs(1, 0);

    ll ans = 0;
    for(auto [k, v] : mst[1])
        ans += v;

    cout << ans << '\n';
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int t = 1;
    if(test_case)cin >> t;
    while(t --)solve();
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 0 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 0 / 17