oj.uz

Submission #1005828

# Submission time Handle Problem Language Result Execution time Memory
1005828 2024-06-23T06:39:23 Z omsincoconut Fireworks (APIO16_fireworks) C++17
7 / 100
 2 ms 12772 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

const ll MAXN = 3e5+5;

ll N, M, P[MAXN], C[MAXN];
vector<ll> child[MAXN];

struct MedianFinder{
    ll n = 0;
    priority_queue<ll> low, high;

    void normalize() {
        while (low.size() > (n>>1)) {
            high.push(-low.top());
            low.pop();
        }
        while (high.size() > (n>>1)) {
            low.push(-high.top());
            high.pop();
        }
    }

    void insert(ll x) {
        n++;
        if (n == 1 || x < query()) low.push(x);
        else high.push(-x);
        normalize();
    }

    void merge(MedianFinder *target, ll offset = 0) {
        while (!low.empty()) {
            target->insert(low.top() + offset);
            low.pop();
        }
        while (!high.empty()) {
            target->insert(-high.top() + offset);
            high.pop();
        }
    }

    ll query() {
        return low.top();
    }
};

MedianFinder *dt[MAXN];
ll median[MAXN];

void dfs(ll u) {
    dt[u] = new MedianFinder();
    if (u > N) {
        dt[u]->insert(0);
        median[u] = 0;
        return;
    }

    for (ll v : child[u]) dfs(v);
    for (ll v : child[u]) dt[v]->merge(dt[u], C[v]);
    median[u] = dt[u]->query();

    /*ll nextc = child[u][0];
    for (ll v : child[u]) if (dt[v]->n > dt[nextc]->n) nextc = v;

    dt[u] = dt[nextc]*/
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M;
    for (ll i = 2; i <= N+M; i++) cin >> P[i] >> C[i];

    for (ll i = 2; i <= N+M; i++) child[P[i]].push_back(i);

    C[1] = 0;
    dfs(1);

    ll ans = 0;
    for (ll i = 2; i <= N+M; i++) {
        ll df = median[P[i]] - median[i];
        ans += abs(C[i] - df);
    }

    cout << ans;

    return 0;
}

Compilation message

fireworks.cpp: In member function 'void MedianFinder::normalize()':
fireworks.cpp:17:27: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   17 |         while (low.size() > (n>>1)) {
      |                ~~~~~~~~~~~^~~~~~~~
fireworks.cpp:21:28: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   21 |         while (high.size() > (n>>1)) {
      |                ~~~~~~~~~~~~^~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 19.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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