oj.uz

Submission #1009376

# Submission time Handle Problem Language Result Execution time Memory
1009376 2024-06-27T12:30:45 Z imarn Fireworks (APIO16_fireworks) C++14
26 / 100
 5 ms 22012 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
using namespace std;
const int mxn=3e5+5;
vector<int>g[mxn];
ll p[mxn],c[mxn],n;
priority_queue<int>q[mxn];
ll a[mxn]{0};ll b[mxn]{0};
void dfs(int u){
    for(auto v:g[u]){
        if(v>n)continue;
        dfs(v);
        while(a[v]>1){
            a[v]--;
            b[v]+=q[v].top();q[v].pop();
        }
        ll x=q[v].top();q[v].pop();
        ll y=q[v].top();q[v].pop();
        q[v].push(x+c[v]);q[v].push(y+c[v]);
        b[v]-=c[v];
        if(q[v].size()>q[u].size())swap(q[u],q[v]);
        while(!q[v].empty())q[u].push(q[v].top()),q[v].pop();
        a[u]+=a[v];b[u]+=b[v];
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int m;cin>>n>>m;
    for(int i=2;i<=n+m;i++)cin>>p[i]>>c[i],g[p[i]].pb(i);
    for(int i=n+1;i<=n+m;i++){
        q[p[i]].push(c[i]);q[p[i]].push(c[i]);
        b[p[i]]-=c[i];a[p[i]]++;
    }dfs(1);
    while(a[1]>0){
        a[1]--;b[1]+=q[1].top();q[1].pop();
    }cout<<b[1];
}

Subtask #1
7.0 / 7.0

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

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21852 KB Output is correct
2 Correct 3 ms 21980 KB Output is correct
3 Correct 3 ms 21852 KB Output is correct
4 Correct 4 ms 21848 KB Output is correct
5 Correct 4 ms 21796 KB Output is correct
6 Correct 4 ms 21852 KB Output is correct
7 Correct 3 ms 21852 KB Output is correct
8 Correct 4 ms 22012 KB Output is correct
9 Correct 4 ms 22008 KB Output is correct
10 Correct 3 ms 21852 KB Output is correct
11 Correct 4 ms 21964 KB Output is correct
12 Correct 4 ms 21852 KB Output is correct
13 Correct 5 ms 21852 KB Output is correct
14 Correct 3 ms 21852 KB Output is correct
15 Correct 4 ms 22008 KB Output is correct
16 Correct 4 ms 21852 KB Output is correct
17 Correct 3 ms 21852 KB Output is correct
18 Correct 4 ms 21852 KB Output is correct
19 Correct 4 ms 21848 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21852 KB Output is correct
2 Correct 4 ms 21852 KB Output is correct
3 Correct 3 ms 21848 KB Output is correct
4 Correct 3 ms 21852 KB Output is correct
5 Correct 4 ms 21852 KB Output is correct
6 Correct 4 ms 21852 KB Output is correct
7 Correct 4 ms 21852 KB Output is correct
8 Correct 3 ms 21852 KB Output is correct
9 Correct 3 ms 21852 KB Output is correct
10 Correct 4 ms 21848 KB Output is correct
11 Correct 3 ms 21852 KB Output is correct
12 Correct 3 ms 21980 KB Output is correct
13 Correct 3 ms 21852 KB Output is correct
14 Correct 4 ms 21848 KB Output is correct
15 Correct 4 ms 21796 KB Output is correct
16 Correct 4 ms 21852 KB Output is correct
17 Correct 3 ms 21852 KB Output is correct
18 Correct 4 ms 22012 KB Output is correct
19 Correct 4 ms 22008 KB Output is correct
20 Correct 3 ms 21852 KB Output is correct
21 Correct 4 ms 21964 KB Output is correct
22 Correct 4 ms 21852 KB Output is correct
23 Correct 5 ms 21852 KB Output is correct
24 Correct 3 ms 21852 KB Output is correct
25 Correct 4 ms 22008 KB Output is correct
26 Correct 4 ms 21852 KB Output is correct
27 Correct 3 ms 21852 KB Output is correct
28 Correct 4 ms 21852 KB Output is correct
29 Correct 4 ms 21848 KB Output is correct
30 Incorrect 4 ms 21848 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21852 KB Output is correct
2 Correct 4 ms 21852 KB Output is correct
3 Correct 3 ms 21848 KB Output is correct
4 Correct 3 ms 21852 KB Output is correct
5 Correct 4 ms 21852 KB Output is correct
6 Correct 4 ms 21852 KB Output is correct
7 Correct 4 ms 21852 KB Output is correct
8 Correct 3 ms 21852 KB Output is correct
9 Correct 3 ms 21852 KB Output is correct
10 Correct 4 ms 21848 KB Output is correct
11 Correct 3 ms 21852 KB Output is correct
12 Correct 3 ms 21980 KB Output is correct
13 Correct 3 ms 21852 KB Output is correct
14 Correct 4 ms 21848 KB Output is correct
15 Correct 4 ms 21796 KB Output is correct
16 Correct 4 ms 21852 KB Output is correct
17 Correct 3 ms 21852 KB Output is correct
18 Correct 4 ms 22012 KB Output is correct
19 Correct 4 ms 22008 KB Output is correct
20 Correct 3 ms 21852 KB Output is correct
21 Correct 4 ms 21964 KB Output is correct
22 Correct 4 ms 21852 KB Output is correct
23 Correct 5 ms 21852 KB Output is correct
24 Correct 3 ms 21852 KB Output is correct
25 Correct 4 ms 22008 KB Output is correct
26 Correct 4 ms 21852 KB Output is correct
27 Correct 3 ms 21852 KB Output is correct
28 Correct 4 ms 21852 KB Output is correct
29 Correct 4 ms 21848 KB Output is correct
30 Incorrect 4 ms 21848 KB Output isn't correct
31 Halted 0 ms 0 KB -