Submission #106628

#	Time	Username	Problem	Language	Result	Execution time	Memory
106628		lyc	Fireworks (APIO16_fireworks)	C++14	100 / 100	394 ms	73336 KiB

fireworks

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int N = 3e5+5;

int n, m;
vector<ii> al[N];

struct Slope {
    priority_queue<ll> points;
    ll a = 0, b = 0;

    void clean() {
        while (a > 1) {
            --a;
            b += points.top();
            points.pop();
        }
    }
};

void print(priority_queue<ll> pq) { while (!pq.empty()) cout << pq.top() << ' ', pq.pop(); cout << '\n'; }

Slope dfs(int u, int p) 
{
    Slope cur;
    if (SZ(al[u]) == 1 and al[u][0].fi == p) 
        cur.points.push(0), cur.points.push(0), cur.a = 1, cur.b = 0;
    else for (auto v : al[u]) if (v.fi != p) {
        Slope nxt = dfs(v.fi, u);
        ll x = nxt.points.top(); nxt.points.pop();
        ll y = nxt.points.top(); nxt.points.pop();
        nxt.points.push(x+v.sc);
        nxt.points.push(y+v.sc);
        nxt.b -= v.sc;
        //cout << "POINT " << x+v.sc << " " << nxt.a << " " << nxt.b << endl;

        if (SZ(nxt.points) > SZ(cur.points)) swap(nxt, cur);
        while (!nxt.points.empty()) {
            cur.points.push(nxt.points.top());
            nxt.points.pop();
        }
        cur.a += nxt.a; cur.b += nxt.b;
    }
    //cout << u << " :: " << cur.a << " " << cur.b << "\t\t\tSZ " << cur.points.size() << endl;
    cur.clean();
    return cur;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    FOR(i, 2, n+m){
        int p, c; cin >> p >> c;
        al[i].emplace_back(p, c);
        al[p].emplace_back(i, c);
    }

    Slope ans = dfs(1, 0);
    //print(ans.points); cout << ans.points.top() << " " << ans.a << " " << ans.b << endl;
    cout << (ll)ans.points.top()*ans.a + ans.b << '\n';
}

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