oj.uz

Submission #714529

# Submission time Handle Problem Language Result Execution time Memory
714529 2023-03-24T22:53:46 Z Spade1 Fireworks (APIO16_fireworks) C++14
7 / 100
 5 ms 8944 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 = 1e5 + 10;

vector<pii> 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) {
        int 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 5 ms 8916 KB Output is correct
2 Correct 5 ms 8940 KB Output is correct
3 Correct 5 ms 8916 KB Output is correct
4 Correct 4 ms 8936 KB Output is correct
5 Correct 5 ms 8920 KB Output is correct
6 Correct 4 ms 8916 KB Output is correct
7 Correct 5 ms 8916 KB Output is correct
8 Correct 5 ms 8940 KB Output is correct
9 Correct 5 ms 8916 KB Output is correct
10 Correct 4 ms 8916 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Correct 4 ms 8916 KB Output is correct
3 Incorrect 4 ms 8944 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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