oj.uz

Submission #402592

# Submission time Handle Problem Language Result Execution time Memory
402592 2021-05-12T02:45:28 Z qwerasdfzxcl Fireworks (APIO16_fireworks) C++14
7 / 100
 6 ms 7372 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
vector<pair<int, int>> adj[300300];
pair<ll, ll> ran[300300];
priority_queue<ll> pq1;
priority_queue<ll, vector<ll>, greater<ll>> pq2;
ll dp[300300];

void ins(ll x, ll y){
    vector<ll> tmp;
    int c=0;
    while(!pq1.empty() && c<2){
        tmp.push_back(pq1.top());
        tmp.push_back(pq2.top());
        pq1.pop();pq2.pop();
        c++;
    }
    tmp.push_back(x);
    tmp.push_back(y);
    sort(tmp.begin(), tmp.end());
    for (int i=0;i<(int)tmp.size()/2;i++) pq1.push(tmp[i]);
    for (int i=(int)tmp.size()/2;i<(int)tmp.size();i++) pq2.push(tmp[i]);
}

ll calc(ll val, ll s, ll e){
    if (s<=val && val<=e) return 0;
    if (e<val) return val-e;
    return s-val;
}

void dfs(int s, ll cur){
    if (adj[s].empty()){
        ran[s] = {cur, cur}, dp[s] = 0;
        return;
    }
    for (auto &v:adj[s]) dfs(v.first, cur+v.second);
    for (auto &v:adj[s]) ins(ran[v.first].first, ran[v.first].second);
    ran[s] = {pq1.top(), pq2.top()};
    ll tmp=0;
    for (auto &v:adj[s]){
        dp[s] += calc(ran[s].first, ran[v.first].first, ran[v.first].second)+dp[v.first];
        tmp += calc(ran[s].second, ran[v.first].first, ran[v.first].second)+dp[v.first];
    }
    assert(tmp==dp[s]);
    while(!pq1.empty()) pq1.pop();
    while(!pq2.empty()) pq2.pop();
    //printf("%d: %lld %lld %lld\n", s, ran[s].first, ran[s].second, dp[s]);
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i=2;i<=n+m;i++){
        int p, c;
        scanf("%d %d", &p, &c);
        adj[p].push_back({i, c});
    }
    dfs(1, 0);
    printf("%lld\n", dp[1]);
    return 0;
}

Compilation message

fireworks.cpp: In function 'int main()':
fireworks.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
fireworks.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d %d", &p, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7244 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Incorrect 6 ms 7244 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 7244 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Correct 5 ms 7244 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 5 ms 7244 KB Output is correct
7 Correct 5 ms 7244 KB Output is correct
8 Correct 6 ms 7372 KB Output is correct
9 Correct 5 ms 7372 KB Output is correct
10 Correct 5 ms 7244 KB Output is correct
11 Correct 5 ms 7244 KB Output is correct
12 Correct 5 ms 7244 KB Output is correct
13 Incorrect 6 ms 7244 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 7244 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Correct 5 ms 7244 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 5 ms 7244 KB Output is correct
7 Correct 5 ms 7244 KB Output is correct
8 Correct 6 ms 7372 KB Output is correct
9 Correct 5 ms 7372 KB Output is correct
10 Correct 5 ms 7244 KB Output is correct
11 Correct 5 ms 7244 KB Output is correct
12 Correct 5 ms 7244 KB Output is correct
13 Incorrect 6 ms 7244 KB Output isn't correct
14 Halted 0 ms 0 KB -