Submission #1183997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183997		SSKMF	Harbingers (CEOI09_harbingers)	C++20	100 / 100	102 ms	31368 KiB

harbingers

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

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

Dreapta candidat[100001];
vector < pair <int , int> > adiacenta[100001];
int termen[100001] , factor[100001] , adancime[100001];
pair <int , int> urmatorul[100001][18];

inline long double Intersectie (const int indice_1 , const int indice_2)
{
    return (long double)(candidat[indice_2].termen - candidat[indice_1].termen) / (candidat[indice_1].panta - candidat[indice_2].panta);
}

inline int64_t Query (int indice , const int valoare)
{
    int exponent = 0;
    while ((1 << (exponent + 1)) <= adancime[indice])
        { exponent++; }

    for ( ; exponent >= 0 ; exponent--) {
        if ((1 << exponent) <= adancime[indice] && Intersectie(urmatorul[indice][exponent].first , urmatorul[indice][exponent].second) > valoare)
            { indice = urmatorul[indice][exponent].first; }
    }

    return candidat[indice](valoare);
}

inline void Parcurgere (const int nod , const int sursa)
{
    if (nod != 1)
        { candidat[nod].termen = termen[nod] - candidat[nod].panta * factor[nod] + Query(sursa , factor[nod]); }

    int __sursa = sursa;
    adancime[nod] = adancime[__sursa] + 1;
    for (int exponent = 17 ; exponent >= 0 ; exponent--) {
        if ((1 << exponent) <= adancime[__sursa] && Intersectie(urmatorul[__sursa][exponent].first , nod) <= Intersectie(urmatorul[__sursa][exponent].first , urmatorul[__sursa][exponent].second))
            { adancime[nod] -= (1 << exponent); __sursa = urmatorul[__sursa][exponent].first; }
    }

    urmatorul[nod][0] = {__sursa , nod};
    for (int exponent = 1 ; (1 << exponent) <= adancime[nod] ; exponent++)
        { urmatorul[nod][exponent] = urmatorul[urmatorul[nod][exponent - 1].first][exponent - 1]; }

    for (auto vecin : adiacenta[nod]) {
        if (vecin.first != sursa)
        {
            candidat[vecin.first].panta = candidat[nod].panta - vecin.second;
            Parcurgere(vecin.first , nod);
        }
    }
}

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

    candidat[1].termen = 0;
    Parcurgere(1 , 0);

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

    return 0;
}

• Subtask 1: 100 / 100