oj.uz

Submission #714530

# Submission time Handle Problem Language Result Execution time Memory
714530 2023-03-24T23:00:04 Z Spade1 Fireworks (APIO16_fireworks) C++14
7 / 100
 16 ms 26268 KB 
#include<bits/stdc++.h>
//#include <grader.h>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ld long double
#define st first
#define nd second
#define pb push_back
#define INF INT_MAX
using namespace std;

const int N = 3e5 + 10;

vector<pll> adj[N];
priority_queue<ll> L[N];
priority_queue<ll, vector<ll>, greater<ll>> R[N];
ll ans[N];

void add(int i, int a, int b) {
    if (!L[i].empty() && a >= L[i].top()) {
        R[i].push(a); R[i].push(b);
        L[i].push(R[i].top()); R[i].pop();
        ans[i] += a-L[i].top();
    }
    else {
        L[i].push(a); L[i].push(b);
        R[i].push(L[i].top()); L[i].pop();
        ans[i] += R[i].top()-b;
    }
}

void dfs(int i) {
    if (adj[i].empty()) {
        L[i].push(0);
        R[i].push(0);
        ans[i] = 0;
        return;
    }
    for (auto [j, w] : adj[i]) {
        dfs(j);
        ans[i] += ans[j];
        int a = L[j].top() + w;
        int b = R[j].top() + w;
        add(i, a, b);
    }
    ll save;
    save = L[i].top();
    while (!L[i].empty()) L[i].pop();
    L[i].push(save);
    save = R[i].top();
    while (!R[i].empty()) R[i].pop();
    R[i].push(save);
}

void solve() {
    int n, m; cin >> n >> m;
    for (int i = 2; i <= n+m; ++i) {
        ll p, c; cin >> p >> c;
        adj[p].pb({i, c});
    }
    dfs(1);
    cout << ans[1] << '\n';
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Compilation message

fireworks.cpp: In function 'void dfs(int)':
fireworks.cpp:40:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |     for (auto [j, w] : adj[i]) {
      |               ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 26068 KB Output is correct
2 Correct 13 ms 26132 KB Output is correct
3 Correct 13 ms 26168 KB Output is correct
4 Correct 13 ms 26168 KB Output is correct
5 Correct 13 ms 26068 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 12 ms 26068 KB Output is correct
8 Correct 12 ms 26268 KB Output is correct
9 Correct 13 ms 26160 KB Output is correct
10 Correct 12 ms 26164 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26104 KB Output is correct
2 Correct 16 ms 26068 KB Output is correct
3 Incorrect 14 ms 26164 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 26068 KB Output is correct
2 Correct 13 ms 26132 KB Output is correct
3 Correct 13 ms 26168 KB Output is correct
4 Correct 13 ms 26168 KB Output is correct
5 Correct 13 ms 26068 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 12 ms 26068 KB Output is correct
8 Correct 12 ms 26268 KB Output is correct
9 Correct 13 ms 26160 KB Output is correct
10 Correct 12 ms 26164 KB Output is correct
11 Correct 12 ms 26104 KB Output is correct
12 Correct 16 ms 26068 KB Output is correct
13 Incorrect 14 ms 26164 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 26068 KB Output is correct
2 Correct 13 ms 26132 KB Output is correct
3 Correct 13 ms 26168 KB Output is correct
4 Correct 13 ms 26168 KB Output is correct
5 Correct 13 ms 26068 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 12 ms 26068 KB Output is correct
8 Correct 12 ms 26268 KB Output is correct
9 Correct 13 ms 26160 KB Output is correct
10 Correct 12 ms 26164 KB Output is correct
11 Correct 12 ms 26104 KB Output is correct
12 Correct 16 ms 26068 KB Output is correct
13 Incorrect 14 ms 26164 KB Output isn't correct
14 Halted 0 ms 0 KB -