oj.uz

Submission #714532

# Submission time Handle Problem Language Result Execution time Memory
714532 2023-03-24T23:10:43 Z Spade1 Fireworks (APIO16_fireworks) C++14
7 / 100
 21 ms 26172 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];
        ll a = L[j].top() + w;
        ll 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 17 ms 26068 KB Output is correct
2 Correct 21 ms 26136 KB Output is correct
3 Correct 18 ms 26148 KB Output is correct
4 Correct 16 ms 26088 KB Output is correct
5 Correct 19 ms 26068 KB Output is correct
6 Correct 14 ms 26100 KB Output is correct
7 Correct 16 ms 26172 KB Output is correct
8 Correct 16 ms 26164 KB Output is correct
9 Correct 18 ms 26068 KB Output is correct
10 Correct 15 ms 26128 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26068 KB Output is correct
2 Correct 12 ms 26068 KB Output is correct
3 Incorrect 12 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 17 ms 26068 KB Output is correct
2 Correct 21 ms 26136 KB Output is correct
3 Correct 18 ms 26148 KB Output is correct
4 Correct 16 ms 26088 KB Output is correct
5 Correct 19 ms 26068 KB Output is correct
6 Correct 14 ms 26100 KB Output is correct
7 Correct 16 ms 26172 KB Output is correct
8 Correct 16 ms 26164 KB Output is correct
9 Correct 18 ms 26068 KB Output is correct
10 Correct 15 ms 26128 KB Output is correct
11 Correct 12 ms 26068 KB Output is correct
12 Correct 12 ms 26068 KB Output is correct
13 Incorrect 12 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 17 ms 26068 KB Output is correct
2 Correct 21 ms 26136 KB Output is correct
3 Correct 18 ms 26148 KB Output is correct
4 Correct 16 ms 26088 KB Output is correct
5 Correct 19 ms 26068 KB Output is correct
6 Correct 14 ms 26100 KB Output is correct
7 Correct 16 ms 26172 KB Output is correct
8 Correct 16 ms 26164 KB Output is correct
9 Correct 18 ms 26068 KB Output is correct
10 Correct 15 ms 26128 KB Output is correct
11 Correct 12 ms 26068 KB Output is correct
12 Correct 12 ms 26068 KB Output is correct
13 Incorrect 12 ms 26164 KB Output isn't correct
14 Halted 0 ms 0 KB -