Submission #1280018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280018		SSKMF	Factories (JOI14_factories)	C++20	100 / 100	3983 ms	149652 KiB

factories

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

pair <int , long long> adancime[500001];
vector < pair <int , int> > adiacenta[500001];
int cantitate[500001] , sursa[500001] , inceput[500001] , tabel[21][1000001] , moment[500001];
long long minim[500001];
bool vizitat[500001];

inline int Combina (const int nod_1 , const int nod_2)
{
    return adancime[nod_1].first < adancime[nod_2].first ? nod_1 : nod_2;
}

inline int LCA (int nod_1 , int nod_2)
{
    nod_1 = inceput[nod_1];
    nod_2 = inceput[nod_2];

    if (nod_1 > nod_2)
        { swap(nod_1 , nod_2); }

    int exponent = 0;
    while ((1 << (exponent + 1)) <= nod_2 - nod_1 + 1)
        { exponent++; }

    return Combina(tabel[exponent][nod_1] , tabel[exponent][nod_2 - (1 << exponent) + 1]);
}

inline long long Distanta (int nod_1 , int nod_2)
{
    return adancime[nod_1].second + adancime[nod_2].second - 2 * adancime[LCA(nod_1 , nod_2)].second;
}

inline void BuildRMQ (const int nod , const int __sursa)
{
    tabel[0][++tabel[0][0]] = nod;
    inceput[nod] = tabel[0][0];

    for (auto& vecin : adiacenta[nod]) {
        if (vecin.first != __sursa)
        {
            adancime[vecin.first] = {adancime[nod].first + 1 , adancime[nod].second + vecin.second};
            BuildRMQ(vecin.first , nod);
            tabel[0][++tabel[0][0]] = nod;
        }
    }
}

inline void Parcurgere (const int nod , const int __sursa)
{
    cantitate[nod] = 1;
    for (auto& vecin : adiacenta[nod]) {
        if (!vizitat[vecin.first] && vecin.first != __sursa)
        {
            Parcurgere(vecin.first , nod);
            cantitate[nod] += cantitate[vecin.first];
        }
    }
}

inline int GetCentroid (int nod)
{
    Parcurgere(nod , 0);
    while (true)
    {
        bool gasit = false;
        for (auto& vecin : adiacenta[nod]) {
            if (!vizitat[vecin.first] && cantitate[vecin.first] > cantitate[nod] / 2)
            {
                cantitate[nod] -= cantitate[vecin.first];
                cantitate[vecin.first] += cantitate[nod];
                nod = vecin.first;
                gasit = true;
                break;
            }
        }

        if (!gasit)
            { break; }
    }

    return nod;
}

inline void Build (int nod , const int anterior)
{
    nod = GetCentroid(nod);
    vizitat[nod] = true;
    sursa[nod] = anterior;
    for (auto& vecin : adiacenta[nod]) {
        if (!vizitat[vecin.first])
            { Build(vecin.first , nod); }
    }
}

void Init (int numar_noduri , int capat_1[] , int capat_2[] , int distanta[])
{
    for (int indice = 0 ; indice < numar_noduri - 1 ; indice++)
    {
        adiacenta[capat_1[indice] + 1].emplace_back(capat_2[indice] + 1 , distanta[indice]);
        adiacenta[capat_2[indice] + 1].emplace_back(capat_1[indice] + 1 , distanta[indice]);
    }

    BuildRMQ(1 , 0);

    for (int exponent = 1 , putere = 2 ; putere <= tabel[0][0] ; exponent++ , putere <<= 1) {
        for (int indice = 1 ; indice + putere - 1 <= tabel[0][0] ; indice++)
            { tabel[exponent][indice] = Combina(tabel[exponent - 1][indice] , tabel[exponent - 1][indice + (putere >> 1)]); }
    }

    Build(1 , 0);
}

inline void Activate (int nod)
{
    const int initial = nod;
    for ( ; nod ; nod = sursa[nod]) {
        if (moment[nod] != moment[0])
            { moment[nod] = moment[0]; minim[nod] = INT64_MAX; }
        minim[nod] = min(minim[nod] , Distanta(initial , nod));
    }
}

inline long long Query (int nod)
{
    const int initial = nod;
    long long rezultat = INT64_MAX;
    for ( ; nod ; nod = sursa[nod]) {
        if (moment[nod] != moment[0])
            { continue; }
        rezultat = min(rezultat , Distanta(nod , initial) + minim[nod]);
    }

    return rezultat;
}

long long Query (int cantitate_1 , int sir_1[] , int cantitate_2 , int sir_2[])
{
    moment[0]++;
    for (int indice = 0 ; indice < cantitate_1 ; indice++)
        { Activate(sir_1[indice] + 1); }

    long long rezultat = INT64_MAX;
    for (int indice = 0 ; indice < cantitate_2 ; indice++)
        { rezultat = min(rezultat , Query(sir_2[indice] + 1)); }

    return rezultat;
}

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67