Submission #1245562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245562		franuch	Tree (IOI24_tree)	C++20	0 / 100	2093 ms	17120 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back
const ll INF = 1e18;

ll V;
vc<ll> par, wgh;
vc<vc<ll>> g;

ll x = 0;

void init(vc<int> P, vc<int> W) {
        par.assign(all(P));
        wgh.assign(all(W));
        V = sz(par);
        g.assign(V, vc<ll>());
        for (ll v = 1; v < V; v++)
                g[par[v]].pub(v);

        for (ll v = 0; v < V; v++)
                x += abs(sz(g[v]) - 1);
}

ll query(int _L, int _R) {
        ll L = _L;
        ll R = _R;
        ll ans = x * L;
        priority_queue<pll> pq;
        for (ll v = 0; v < V; v++)
                if (sz(g[v]) >= 2)
                        pq.push({wgh[v], sz(g[v]) - 1});

        for (ll i = L; i < R; i++) {
                if (pq.empty())
                        break;
                pll p = pq.top();
                pq.pop();
                ans -= p.st;
                if (p.nd >= 2)
                        pq.push({p.st, p.nd - 1});
        }
        return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 18
• Subtask 4: 0 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19