oj.uz

Submission #1092151

# Submission time Handle Problem Language Result Execution time Memory
1092151 2024-09-23T10:37:29 Z ASN49K Fireworks (APIO16_fireworks) C++14
26 / 100
 11 ms 21636 KB 
#include <bits/stdc++.h>
using namespace std;
using i64=long long;
#define UNUSED -1
#define all(x) x.begin(),x.end()
#define pb push_back
const int mod=1e9+7,inf=1e9+1;
const int N=3e5;
vector<pair<int,int>>g[N];
multiset<i64>mp[N];
i64 rez[N];
void dfs(int nod)
{
    if(g[nod].size()==0)
    {
        mp[nod].insert(0);
        mp[nod].insert(0);
        return;
    }
    for(auto &c:g[nod])
    {
        dfs(c.first);
        int v1=*mp[c.first].rbegin();
        mp[c.first].erase(mp[c.first].find(v1));
        int v2=*mp[c.first].rbegin();
        mp[c.first].erase(mp[c.first].find(v2));

        mp[c.first].insert(v1+c.second);
        mp[c.first].insert(v2+c.second);


        if(mp[nod].size() < mp[c.first].size())
        {
            swap(mp[nod] , mp[c.first]);
        }
        for(auto &v:mp[c.first])
        {
            mp[nod].insert(v);
        }
    }
    for(int i=1;i<(int)g[nod].size();i++)
    {
        mp[nod].erase(mp[nod].find(*mp[nod].rbegin()));
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    n+=m;

    i64 rez=0;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        rez+=y;
        x--;
        g[x].pb({i,y});
    }
    dfs(0);
    i64 last=0;
    for(int i=m;i>0;i--)
    {
        i64 it=*mp[0].begin();
        mp[0].erase(mp[0].find(it));
        rez+=(last-it)*i;
        last=it;
    }
    cout<<rez;
}
/*
4 6
1 5
2 5
2 8
3 3
3 2
3 3
2 9
4 4
4 3
*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 21596 KB Output is correct
2 Correct 9 ms 21340 KB Output is correct
3 Correct 8 ms 21596 KB Output is correct
4 Correct 8 ms 21616 KB Output is correct
5 Correct 9 ms 21592 KB Output is correct
6 Correct 9 ms 21544 KB Output is correct
7 Correct 9 ms 21596 KB Output is correct
8 Correct 9 ms 21496 KB Output is correct
9 Correct 8 ms 21596 KB Output is correct
10 Correct 9 ms 21596 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 21596 KB Output is correct
2 Correct 9 ms 21592 KB Output is correct
3 Correct 9 ms 21596 KB Output is correct
4 Correct 8 ms 21596 KB Output is correct
5 Correct 9 ms 21504 KB Output is correct
6 Correct 9 ms 21432 KB Output is correct
7 Correct 11 ms 21596 KB Output is correct
8 Correct 9 ms 21596 KB Output is correct
9 Correct 9 ms 21368 KB Output is correct
10 Correct 9 ms 21468 KB Output is correct
11 Correct 8 ms 21596 KB Output is correct
12 Correct 8 ms 21592 KB Output is correct
13 Correct 8 ms 21596 KB Output is correct
14 Correct 9 ms 21608 KB Output is correct
15 Correct 9 ms 21592 KB Output is correct
16 Correct 10 ms 21636 KB Output is correct
17 Correct 9 ms 21596 KB Output is correct
18 Correct 9 ms 21492 KB Output is correct
19 Correct 10 ms 21596 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 21596 KB Output is correct
2 Correct 9 ms 21340 KB Output is correct
3 Correct 8 ms 21596 KB Output is correct
4 Correct 8 ms 21616 KB Output is correct
5 Correct 9 ms 21592 KB Output is correct
6 Correct 9 ms 21544 KB Output is correct
7 Correct 9 ms 21596 KB Output is correct
8 Correct 9 ms 21496 KB Output is correct
9 Correct 8 ms 21596 KB Output is correct
10 Correct 9 ms 21596 KB Output is correct
11 Correct 8 ms 21596 KB Output is correct
12 Correct 9 ms 21592 KB Output is correct
13 Correct 9 ms 21596 KB Output is correct
14 Correct 8 ms 21596 KB Output is correct
15 Correct 9 ms 21504 KB Output is correct
16 Correct 9 ms 21432 KB Output is correct
17 Correct 11 ms 21596 KB Output is correct
18 Correct 9 ms 21596 KB Output is correct
19 Correct 9 ms 21368 KB Output is correct
20 Correct 9 ms 21468 KB Output is correct
21 Correct 8 ms 21596 KB Output is correct
22 Correct 8 ms 21592 KB Output is correct
23 Correct 8 ms 21596 KB Output is correct
24 Correct 9 ms 21608 KB Output is correct
25 Correct 9 ms 21592 KB Output is correct
26 Correct 10 ms 21636 KB Output is correct
27 Correct 9 ms 21596 KB Output is correct
28 Correct 9 ms 21492 KB Output is correct
29 Correct 10 ms 21596 KB Output is correct
30 Incorrect 9 ms 21596 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 21596 KB Output is correct
2 Correct 9 ms 21340 KB Output is correct
3 Correct 8 ms 21596 KB Output is correct
4 Correct 8 ms 21616 KB Output is correct
5 Correct 9 ms 21592 KB Output is correct
6 Correct 9 ms 21544 KB Output is correct
7 Correct 9 ms 21596 KB Output is correct
8 Correct 9 ms 21496 KB Output is correct
9 Correct 8 ms 21596 KB Output is correct
10 Correct 9 ms 21596 KB Output is correct
11 Correct 8 ms 21596 KB Output is correct
12 Correct 9 ms 21592 KB Output is correct
13 Correct 9 ms 21596 KB Output is correct
14 Correct 8 ms 21596 KB Output is correct
15 Correct 9 ms 21504 KB Output is correct
16 Correct 9 ms 21432 KB Output is correct
17 Correct 11 ms 21596 KB Output is correct
18 Correct 9 ms 21596 KB Output is correct
19 Correct 9 ms 21368 KB Output is correct
20 Correct 9 ms 21468 KB Output is correct
21 Correct 8 ms 21596 KB Output is correct
22 Correct 8 ms 21592 KB Output is correct
23 Correct 8 ms 21596 KB Output is correct
24 Correct 9 ms 21608 KB Output is correct
25 Correct 9 ms 21592 KB Output is correct
26 Correct 10 ms 21636 KB Output is correct
27 Correct 9 ms 21596 KB Output is correct
28 Correct 9 ms 21492 KB Output is correct
29 Correct 10 ms 21596 KB Output is correct
30 Incorrect 9 ms 21596 KB Output isn't correct
31 Halted 0 ms 0 KB -