Submission #68511

#	Time	Username	Problem	Language	Result	Execution time	Memory
68511		chpipis	Fireworks (APIO16_fireworks)	C++11	100 / 100	304 ms	128804 KiB

fireworks

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)

// START for segment tree
#define params int p, int L, int R
#define housekeep int mid = (L + R) >> 1, left = p << 1, right = left | 1
// END

#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
    advance(it, -n);
    return it;
}

template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
    advance(it, n);
    return it;
}
#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

template<typename T>
inline T sq(T a) { return a * a; }

//#ifdef LOCAL_MACHINE
//#endif

const int MAXN = 3e5 + 5;

int p[MAXN], c[MAXN];
ll a[MAXN], b[MAXN];
priority_queue<ll> *pq[MAXN];

int main() {
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 2; i <= n + m; i++) {
        scanf("%d %d", &p[i], &c[i]);
    }
    for (int i = n + m; i > n; i--) {
        a[i] = 1;
        b[i] = -c[i];
        pq[i] = new priority_queue<ll>();
        pq[i]->push(c[i]);
        pq[i]->push(c[i]);
        if (pq[p[i]] == NULL) {
            pq[p[i]] = pq[i];
            a[p[i]] = a[i];
            b[p[i]] = b[i];
        } else {
            if (pq[p[i]]->size() < pq[i]->size())
                swap(pq[p[i]], pq[i]);
            while (pq[i]->size()) {
                pq[p[i]]->push(pq[i]->top());
                pq[i]->pop();
            }
            a[p[i]] += a[i];
            b[p[i]] += b[i];
        }
    }
    for (int i = n; i >= 1; i--) {
        while (a[i] > 1) {
            a[i]--;
            b[i] += pq[i]->top();
            pq[i]->pop();
        }
        ll p2 = pq[i]->top();
        pq[i]->pop();
        ll p1 = pq[i]->top();
        pq[i]->pop();
        b[i] -= c[i];
        pq[i]->push(p1 + c[i]);
        pq[i]->push(p2 + c[i]);
        if (i == 1) break;
        if (pq[p[i]] == NULL) {
            pq[p[i]] = pq[i];
            a[p[i]] = a[i];
            b[p[i]] = b[i];
        } else {
            if (pq[p[i]]->size() < pq[i]->size())
                swap(pq[p[i]], pq[i]);
            while (pq[i]->size()) {
                pq[p[i]]->push(pq[i]->top());
                pq[i]->pop();
            }
            a[p[i]] += a[i];
            b[p[i]] += b[i];
        }
    }
    printf("%lld\n", pq[1]->top() * a[1] + b[1]);
    return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
fireworks.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &p[i], &c[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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