oj.uz

Submission #610931

# Submission time Handle Problem Language Result Execution time Memory
610931 2022-07-28T19:07:52 Z _maks2000 Fireworks (APIO16_fireworks) C++17
0 / 100
 1 ms 212 KB 
#include<iostream>
#include<vector>
#include<set>

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[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 ;
    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 ;
}

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

    /*
    dp[i]=
    {
        jesli lisc, to wartosc
        inaczej przejdz po dzieciach i stworz funkcje
        nastepnie oblicz optymalna wartosc
        przejdz po dzieciach jeszcze raz oblicz koszt
        dodaj koszt do wyniku i przejdz dalej
    }
    */
    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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -