Submission #1254838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254838		shjeong	Fireworks (APIO16_fireworks)	C++20	100 / 100	319 ms	93096 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define COMP(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define MOD2 998244353
#define sz(x) (ll)x.size()
typedef __int128_t lll;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ll, pll> PP;
const ll Lnf = 2e18;
ll n, m;
vector<array<ll,2>> adj[303030];
ll w[303030];   //부모 간선의 가중치
ll num[303030];
priority_queue<ll> pq[303030];
ll b[303030];
void dfs(ll x){
    ll a = 0;
    pq[num[x]].push(0);
    pq[num[x]].push(0);
    for(auto [next,w] : adj[x]){
        dfs(next);
        a++;
        b[x] += b[next];
        if(sz(pq[num[x]]) < sz(pq[num[next]]))swap(num[x],num[next]);
        while(sz(pq[num[next]]))pq[num[x]].push(pq[num[next]].top()), pq[num[next]].pop();
    }
    while(a>1){
        a--;
        b[x] += pq[num[x]].top(); pq[num[x]].pop();
    }
//    cout<<x<<" "<<pq[num[x]].top()<<" "<<b[x]<<endl;
    ll r = pq[num[x]].top(); pq[num[x]].pop();
    ll l = pq[num[x]].top(); pq[num[x]].pop();
    pq[num[x]].push(l+w[x]); pq[num[x]].push(r+w[x]);
    b[x] -= w[x];
    if(x==1)cout<<pq[num[x]].top() + b[x];
//    cout<<x<<" "<<pq[num[x]].top()<<" "<<b[x]<<endl;
}
int main(){
    fast;
    cin>>n>>m;
    for(int i = 1 ; i <= n+m ; i++)num[i]=i;
    for(int i = 2 ; i <= n+m ; i++){
        ll p; cin>>p>>w[i];
        adj[p].push_back({i,w[i]});
    }
    dfs(1);
}

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