제출 #244212

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
244212		WhaleVomit	Fireworks (APIO16_fireworks)	C++14	100 / 100	286 ms	57076 KiB

fireworks

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

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()

#define MOO(i, a, b) for(int i=a; i<b; i++)
#define M00(i, a) for(int i=0; i<a; i++)
#define MOOd(i,a,b) for(int i = (b)-1; i >= a; i--)
#define M00d(i,a) for(int i = (a)-1; i>=0; i--)

#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << '\n', 0;
#define dbg(x) cerr << ">>> " << #x << " = " << x << "\n";
#define _ << " _ " <<

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef pair<ld,ld> pd;
typedef complex<ld> cd;

struct func {
    priority_queue<ll> changes;
    ll a, b;
    func(ll k) { // makes y=|x-k| graph
        a = 1;
        b = -k;
        changes.push(k); changes.push(k);
    }
};

const int MAX_N = 300300;
int n;
ll len[MAX_N];
vi ch[MAX_N];

func* sumtwo(func* f1, func* f2) {
    if(sz(f1->changes) < sz(f2->changes)) swap(f1, f2);
    while(!(f2->changes).empty()) {
        (f1->changes).push((f2->changes).top());
        (f2->changes).pop();
    }
    f1->a += f2->a;
    f1->b += f2->b;
    return f1;
}

func* sum(vector<func*>& v) {
    func* cur = v[0];
    MOO(i, 1, sz(v)) cur = sumtwo(cur, v[i]);
    return cur;
}

func* get(int u) {
    if(sz(ch[u]) == 0) {
        return new func(len[u]);
    } else {
        vector<func*> stuff;
        for(int v: ch[u]) stuff.pb(get(v));
        func* res = sum(stuff);
        while((res->a) > 1) {
            ll xcoord = (res->changes).top();
            (res->changes).pop();
            (res->a)--;
            (res->b) += xcoord;
        }
        ll s1 = (res->changes).top();
        (res->changes).pop();
        ll s2 = (res->changes).top();
        (res->changes).pop();
        (res->changes).push(s1 + len[u]);
        (res->changes).push(s2 + len[u]);
        (res->b) -= len[u];
        return res;
    }
}

int main() { FAST
    int k1, k2; cin >> k1 >> k2;
    n = k1+k2;
    MOO(i, 1, n) {
        int u; cin >> u; u--;
        ll c; cin >> c;
        len[i] = c;
        ch[u].pb(i);
    }
    func* ans = get(0);
    ll x = (ans->changes).top();
    ll val = x * (ans->a) + (ans->b);
    finish(val);
}

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45