Submission #40017

#	Time	Username	Problem	Language	Result	Execution time	Memory
40017		nickyrio	Fireworks (APIO16_fireworks)	C++14	7 / 100	10 ms	108476 KiB

fireworks

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define Arr(A, l, r) { cerr << #A  << " = "; FOR(_, l, r) cerr << A[_] << ' '; cerr << endl; }
#define N 1000100
#define pp pair<int, int>
#define next __next
#define prev __prev
#define __builtin_popcount __builtin_popcountll
#define bit(S, i) (((S) >> i) & 1)
#define IO cin.tie(NULL);cout.tie(NULL);
using namespace std;

int n, p[N], val[N], status[N], total, Del[N], DEG[N];
long long IT[N << 2], lazy[N << 2];;
bool Disabled[N];
vector<pp> e[N];


void dfs(int u) {
    for (pp t : e[u]) {
        int v = t.first;
        int c = t.second;
        if (v != p[u]) {
            p[v] = u;
            val[v] = c;
            dfs(v);
        }
    }
}

void Build(int k, int l, int r) {
    lazy[k] = 0;
    if (l == r) {
        if (l <= n) {
            IT[k] = 1e18;
            Disabled[l] = true;
        }
        else {
            IT[k] = val[l];
            Disabled[l] = false;
            status[l] = 1;
            total++;
        }
        return;
    }
    int m = (l + r) >> 1;
    Build(k << 1, l, m);
    Build(k << 1 | 1, m + 1, r);
    IT[k] = min(IT[k << 1], IT[k << 1 | 1]);
}

void Down(int k) {
    if (lazy[k] == 0) return;
    lazy[k << 1] += lazy[k];
    lazy[k << 1 | 1] += lazy[k];
    IT[k << 1] += lazy[k];
    IT[k << 1 | 1] += lazy[k];
    lazy[k] = 0;
}

void Set(int k, int l, int r, int u, int val) {
    if (l == r) {
        IT[k] = val;
        lazy[k] = 0;
        return;
    }
    Down(k);
    int m = (l + r) >> 1;
    if (u <= m) Set(k << 1, l, m, u, val);
    else Set(k << 1 | 1, m + 1, r, u, val);
    IT[k] = min(IT[k << 1], IT[k << 1 | 1]);
}

void Research(int k, int l, int r) {
    if (IT[k] > 0) return;
    if (l == r) {
        Disabled[l] = true;
        IT[k] = 1e18;
        total -= 2;
        status[l] = -1;
        if (p[l] == -1) return;
        Del[p[l]]++;
        if (Del[p[l]] * 2 >= (int)e[p[l]].size() - (p[l] != 1)) {
            for (pp t : e[p[l]]) {
                int v = t.first;
                if (v != p[p[l]]) {
                    total -= status[v];
                    status[v] = 0;
                    if (!Disabled[v]) {
                        Set(1, 1, n, v, 1e18);
                        Disabled[v] = true;
                    }
                }
            }
            Disabled[p[l]] = false;
            status[p[l]] = 1;
            total++;
            Set(1, 1, n, p[l], val[p[l]]);
        }
        return;
    }
    Down(k);
    int m = (l + r) >> 1;
    Research(k << 1, l, m);
    Research(k << 1 | 1, m + 1, r);
    IT[k] = min(IT[k << 1], IT[k << 1 | 1]);
}


int main() {
    //Enter
    IO;
    int m;
    cin >> n >> m;
    long long result = 0;
    FOR(i, 2, n + m) {
        int u, c;
        cin >> u >> c;
        result += c;
        e[i].push_back(pp(u, c));
        e[u].push_back(pp(i, c));
        DEG[i]++;
        DEG[u]++;
    }
    p[1] = -1;
    dfs(1);
    // Initialization
    Build(1, 1, n + m);
    n += m;
    // Solve
    while (total > 0) {
        result -= 1ll * IT[1] * total;
        lazy[1] -= IT[1];
        IT[1] = 0;
        Research(1, 1, n);
    }
    cout << result;
}

Compilation message (stderr)

fireworks.cpp: In function 'void Research(int, int, int)':
fireworks.cpp:93:45: warning: overflow in implicit constant conversion [-Woverflow]
                         Set(1, 1, n, v, 1e18);
                                             ^

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