oj.uz

Submission #479925

# Submission time Handle Problem Language Result Execution time Memory
479925 2021-10-14T00:11:40 Z sam571128 Fireworks (APIO16_fireworks) C++17
26 / 100
 1 ms 588 KB 
#include <bits/stdc++.h>
#include <bits/extc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 605, M = 305;
vector<pair<int,int>> adj[N];

int dp[N], to[N], deg[N], ans = 0;

__gnu_pbds::priority_queue<int> pq[N];

void dfs(int u, int p){
    for(auto [v,w] : adj[u]){
        if(v == p) continue;
        dfs(v,u);
        pq[u].join(pq[v]);
    }

    if(u==1) return;

    int l = 0, r = 0;

    if(deg[u]){
        while(--deg[u]){
            pq[u].pop();
        }

        r = pq[u].top();
        pq[u].pop();

        l = pq[u].top();
        pq[u].pop();
    }

    pq[u].push(l+to[u]);
    pq[u].push(r+to[u]);
}

signed main(){
    fastio
    int n,m;
    cin >> n >> m;
    for(int i = 2;i <= n;i++){
        int p,x;
        cin >> p >> x;
        to[i] = x;
        adj[p].push_back({i,x});
        adj[i].push_back({p,x});
        deg[p]++;
        ans += x;
    }
    for(int i = 1;i <= m;i++){
        int p,x;
        cin >> p >> x;
        to[n+i] = x;
        adj[p].push_back({i+n,x});
        adj[i+n].push_back({p,x});
        deg[p]++;
        ans += x;
    }

    dfs(1,-1);

    while(deg[1]--){
        pq[1].pop();
    }

    while(!pq[1].empty()){
        ans -= pq[1].top();
        pq[1].pop();
    }


    cout << ans << "\n";
}

Subtask #1
7.0 / 7.0

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

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 332 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Runtime error 1 ms 588 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Runtime error 1 ms 588 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -