oj.uz

Submission #40017

# Submission time Handle Problem Language Result Execution time Memory
40017 2018-01-25T10:14:20 Z nickyrio Fireworks (APIO16_fireworks) C++14
7 / 100
 10 ms 108476 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 108476 KB Output is correct
2 Correct 3 ms 108476 KB Output is correct
3 Correct 7 ms 108476 KB Output is correct
4 Correct 4 ms 108476 KB Output is correct
5 Correct 6 ms 108476 KB Output is correct
6 Correct 6 ms 108476 KB Output is correct
7 Correct 3 ms 108476 KB Output is correct
8 Correct 10 ms 108476 KB Output is correct
9 Correct 6 ms 108476 KB Output is correct
10 Correct 3 ms 108476 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 108476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 108476 KB Output is correct
2 Correct 3 ms 108476 KB Output is correct
3 Correct 7 ms 108476 KB Output is correct
4 Correct 4 ms 108476 KB Output is correct
5 Correct 6 ms 108476 KB Output is correct
6 Correct 6 ms 108476 KB Output is correct
7 Correct 3 ms 108476 KB Output is correct
8 Correct 10 ms 108476 KB Output is correct
9 Correct 6 ms 108476 KB Output is correct
10 Correct 3 ms 108476 KB Output is correct
11 Incorrect 3 ms 108476 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 108476 KB Output is correct
2 Correct 3 ms 108476 KB Output is correct
3 Correct 7 ms 108476 KB Output is correct
4 Correct 4 ms 108476 KB Output is correct
5 Correct 6 ms 108476 KB Output is correct
6 Correct 6 ms 108476 KB Output is correct
7 Correct 3 ms 108476 KB Output is correct
8 Correct 10 ms 108476 KB Output is correct
9 Correct 6 ms 108476 KB Output is correct
10 Correct 3 ms 108476 KB Output is correct
11 Incorrect 3 ms 108476 KB Output isn't correct
12 Halted 0 ms 0 KB -