Submission #610948

#	Time	Username	Problem	Language	Result	Execution time	Memory
610948		_maks2000	Fireworks (APIO16_fireworks)	C++17	7 / 100	1 ms	212 KiB

fireworks

#include<iostream>
#include<vector>
#include<set>
#define int long long

using namespace std;
typedef pair<int,int>pi;

vector<pi>dp ;
int timee=0,odp=0 ;

vector<int>czas ;

void DFS(int v, int ojciec, int suma, vector<vector<pi>>&V)
{
    //cout << v+1 << endl ;
    czas[v]=timee++ ;
    for(auto [u,du]:V[v])
    {
        if(u==ojciec) continue ;
        DFS(u,v,suma+du,V) ;
    }

    if(v!=0 && V[v].size()==1)
    {
        dp[czas[v]]={suma,suma} ;
        return ;
    }

    multiset<int>S ;
    for(auto [u,du]:V[v])
    {
        if(u==ojciec) continue ;
        auto [x,y]=dp[czas[u]] ;
        S.insert(x) ;
        S.insert(y);
    }
    //cout << v+1 << " " << S.size() << " " ;

    int kat=S.size()/2,minn=0,last=0 ;
    kat*=-1;
    for(auto i:S)
    {
        if(kat==0)
        {
            minn=i ;
            break ;
        }
        kat++ ;
        last=i ;
    }
    dp[czas[v]]={last,minn} ;

    //cout << minn << endl ;

    for(auto [u,du]:V[v])
    {
        if(u==ojciec) continue ;
        auto [x,y]=dp[czas[u]] ;
        int xd=0 ;
        if(minn<x) xd=x-minn ;
        if(minn>y) xd=minn-y;
        odp+=xd;
    }
    return ;
}

int32_t main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0) ;
    std::cout.tie(0);

    int n,m; cin >> n >> m;
    dp.resize(n+m,{-1,-1}),czas.resize(n+m,0) ;
    vector<vector<pi>>V(n+m,vector<pi>()) ;
    for(int i=1;i<n+m;i++)
    {
        int b,c; cin >> b >> c;
        b-- ;
        V[i].push_back({b,c}) ;
        V[b].push_back({i,c}) ;
    }
    DFS(0,0,0,V) ;
    /*
    for(auto [x,y]:dp)
    {
        cout << x << " " << y << endl ;
    }
    */
    cout << odp ;
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45