제출 #471806

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
471806		Windazz	Fireworks (APIO16_fireworks)	C++17	100 / 100	271 ms	70084 KiB

fireworks

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

#define x first
#define y second
#define ndl '\n'
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define up_b upper_bound
#define low_b lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;
//using namespace __gnu_pbds;

//template<typename T> using indexed_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());//uniform_int_distribution<int> (l, r)

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<int, ull> piu;
typedef vector<vector<int>> matrix;

const ll INF = 1e18 + 123;
const ld EPS = 1e-9;
const int inf = 1e9 + 123;
const int MOD = 1e9 + 7;
const int N = 3e5 + 123;
const int M = 1e6 + 123;
const double pi = 3.14159265359;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

struct node{
    ll a = 0, b = 0;
    priority_queue<ll> q;
}dp[N];

vector<int> g[N];

int c[N];

void dfs(int v){
    if (g[v].empty()){
        dp[v].a = -1;
        dp[v].b = c[v];
        dp[v].q.push(c[v]);
        dp[v].q.push(c[v]);
        return;
    }
    for (int to : g[v]){
        dfs(to);
        dp[v].a += dp[to].a;
        dp[v].b += dp[to].b;
        if (sz(dp[v].q) < sz(dp[to].q)){
            swap(dp[v].q, dp[to].q);
        }
        while (!dp[to].q.empty()){
            dp[v].q.push(dp[to].q.top());
            dp[to].q.pop();
        }
    }
    while (dp[v].a + sz(dp[v].q) > 1){
        dp[v].q.pop();
    }
    ll x1 = dp[v].q.top();
    dp[v].q.pop();
    ll x2 = dp[v].q.top();
    dp[v].q.pop();

    dp[v].b += c[v];
    dp[v].q.push(x1+c[v]);
    dp[v].q.push(x2+c[v]);

}
    
void solve(){
    int n, m;
    cin >> n >> m;
    for (int i = 2, p; i <= n+m; i++){
        cin >> p >> c[i];
        g[p].pb(i);
    }
    dfs(1);

    vector<ll> v;

    while (!dp[1].q.empty()) {
        v.push_back(dp[1].q.top());
        dp[1].q.pop();
    }
    v.pb(0);

    for (int i = sz(v)-2; dp[1].a < 0; i--, dp[1].a++){
        dp[1].b += (v[i] - v[i+1]) * dp[1].a;
    }
    cout << dp[1].b;


}

int main(){
    #ifdef me
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;  
    //cin >> t;
    for (int i = 1; i <= t; i++){
        //cout << "Case #" << i << ": ";
        solve();
    }
    #ifdef KAZAKH
      //  cout << endl << 1.0 * clock() / CLOCKS_PER_SEC << endl;
    #endif
    return 0;
}

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