Submission #1280014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280014		SSKMF	공장들 (JOI14_factories)	C++20	0 / 100	8085 ms	92352 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[20][500001] , moment[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)
{
    vizitat[nod] = true;
    nod = GetCentroid(nod);
    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);
}

long long Query (int cantitate_1 , int sir_1[] , int cantitate_2 , int sir_2[])
{
    long long rezultat = INT64_MAX;
    for (int indice_1 = 0 ; indice_1 < cantitate_1 ; indice_1++) {
        for (int indice_2 = 0 ; indice_2 < cantitate_2 ; indice_2++)
            { rezultat = min(rezultat , Distanta(sir_1[indice_1] + 1 , sir_2[indice_2] + 1)); }
    }

    return rezultat;
}

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