제출 #1183977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183977		SSKMF	Harbingers (CEOI09_harbingers)	C++20	0 / 100	139 ms	131072 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;

struct Dreapta {
    int64_t panta = 0 , termen = 1000000000000000LL;
    Dreapta *stanga = NULL , *dreapta = NULL;
    int64_t operator ()(int64_t punct) { return panta * punct + termen; }
};

Dreapta *radacina[18];
vector < pair <int , int> > adiacenta[100001];
int cantitate[100001] , termen[100001] , factor[100001] , adancime[100001];
int64_t minim[100001];

inline void Update (Dreapta* &anterior , Dreapta* &actual , const int stanga , const int dreapta , Dreapta candidat)
{
    if (anterior == actual)
    {
        actual = new Dreapta;
        actual -> panta = anterior -> panta;
        actual -> termen = anterior -> termen;
        actual -> stanga = anterior -> stanga;
        actual -> dreapta = anterior -> dreapta;
    }

    const int mijloc = (stanga + dreapta) >> 1;
    const bool rezultat_1 = ((*actual)(stanga) > candidat(stanga));
    const bool rezultat_2 = ((*actual)(mijloc) > candidat(mijloc));
    if (rezultat_2) { swap(actual -> panta , candidat.panta); swap(actual -> termen , candidat.termen); }

    if (stanga != dreapta) {
        if (rezultat_1 != rezultat_2) { Update(anterior -> stanga , actual -> stanga , stanga , mijloc , candidat); actual -> dreapta = anterior -> dreapta; }
        else { actual -> stanga = anterior -> stanga; Update(anterior -> dreapta , actual -> dreapta , mijloc + 1 , dreapta , candidat); }
    }
}

inline int64_t Query (Dreapta* &nod , const int stanga , const int dreapta , const int indice)
{
    if (stanga == dreapta || nod == radacina[0])
        { return (*nod)(indice); }
    
    const int mijloc = (stanga + dreapta) >> 1;
    return min((*nod)(indice) , (indice <= mijloc ? Query(nod -> stanga , stanga , mijloc , indice) : Query(nod -> dreapta , mijloc + 1 , dreapta , indice)));
}

inline void Clear (Dreapta* &anterior , Dreapta* &actual)
{
    if (anterior == actual)
        { return; }

    Clear(anterior -> stanga , actual -> stanga);
    Clear(anterior -> dreapta , actual -> dreapta);
    delete actual;
}

inline void Precalculare (const int nod , const int sursa)
{
    cantitate[nod] = 1;
    for (auto vecin : adiacenta[nod]) {
        if (vecin.first != sursa)
        {
            adancime[vecin.first] = adancime[nod] + vecin.second;
            Precalculare(vecin.first , nod);
            cantitate[nod] += cantitate[vecin.first];
        }
    }
}

inline void Parcurgere (const int nod , const int sursa , const int indice)
{
    if (nod != 1)
        { minim[nod] = termen[nod] + 1LL * adancime[nod] * factor[nod] + Query(radacina[indice] , 1 , 1000000000 , factor[nod]); }

    Update(radacina[indice - 1] , radacina[indice] , 1 , 1000000000 , {-adancime[nod] , minim[nod]});

    int maxim = 0;
    for (auto vecin : adiacenta[nod]) {
        if (vecin.first != sursa && cantitate[vecin.first] > cantitate[maxim])
            { maxim = vecin.first; }
    }
    
    for (auto vecin : adiacenta[nod]) {
        if (vecin.first != sursa && vecin.first != maxim)
        {
            radacina[indice + 1] = radacina[indice];
            Parcurgere(vecin.first , nod , indice + 1);
            Clear(radacina[indice] , radacina[indice + 1]);
        }
    }

    if (maxim)
        { Parcurgere(maxim , nod , indice); }
}

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int numar_noduri;
    cin >> numar_noduri;

    for (int indice = 1 ; indice < numar_noduri ; indice++)
    {
        int nod[2] , distanta;
        cin >> nod[0] >> nod[1] >> distanta;
        adiacenta[nod[0]].push_back({nod[1] , distanta});
        adiacenta[nod[1]].push_back({nod[0] , distanta});
    }

    for (int indice = 2 ; indice <= numar_noduri ; indice++)
        { cin >> termen[indice] >> factor[indice]; }

    radacina[0] = new Dreapta;
    radacina[0] -> stanga = radacina[0] -> dreapta = radacina[0];
    radacina[1] = radacina[0];
    Precalculare(1 , 0);
    Parcurgere(1 , 0 , 1);

    for (int indice = 2 ; indice <= numar_noduri ; indice++)
        { cout << minim[indice] << ' '; }

    return 0;
}

• Subtask 1: 0 / 100