Submission #249939

#	Time	Username	Problem	Language	Result	Execution time	Memory
249939		receed	Fireworks (APIO16_fireworks)	C++14	100 / 100	581 ms	101240 KiB

fireworks

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;

const int N = 300001;
ll pw[N], sm[N], sz[N];
multiset<ll> s[N];
vector<int> g[N];

void dfs(int v) {
    sm[v] = pw[v];
    for (int u : g[v]) {
        dfs(u);
        sm[v] += sm[u];
        if (s[v].size() < s[u].size())
            swap(s[u], s[v]);
        for (ll i : s[u])
            s[v].insert(i);
    }
    if (!g[v].empty()) {
        rep(i, g[v].size() - 1)
            s[v].erase(--s[v].end());
        ll v1 = *--s[v].end();
        s[v].erase(--s[v].end());
        ll v2 = *--s[v].end();
        s[v].erase(--s[v].end());
        s[v].insert(v1 + pw[v]);
        s[v].insert(v2 + pw[v]);
    }
    else {
        s[v].insert(pw[v]);
        s[v].insert(pw[v]);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll n, m, p, w;
    cin >> n >> m;
    for (int i = 1; i < n + m; i++) {
        cin >> p >> pw[i];
        g[p - 1].push_back(i);
    }
    dfs(0);
    s[0].erase(--s[0].end());
    ll ls = 0, ck = s[0].size(), ans = sm[0];
    for (ll i : s[0]) {
        ans -= (i - ls) * ck;
        ck--;
        ls = i;
    }
    cout << ans;
}

Compilation message (stderr)

fireworks.cpp: In function 'void dfs(int)':
fireworks.cpp:19:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i = 0; i < (n); i++)
                                     ^
fireworks.cpp:44:9: note: in expansion of macro 'rep'
         rep(i, g[v].size() - 1)
         ^~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:61:17: warning: unused variable 'w' [-Wunused-variable]
     ll n, m, p, w;
                 ^

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