제출 #1326112

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326112		SSKMF	경주 (Race) (IOI11_race)	C++20	100 / 100	476 ms	56612 KiB

race

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

static vector < pair <int , int> > adiacenta[200000];
static int inceput[200000] , sfarsit[200000] , ordine[200001] , rezultat = INT32_MAX;
static pair <int , int64_t> adancime[200000];
static map <int64_t , int> candidati;

int Precalculare (const int nod , const int sursa)
{
    ordine[++ordine[0]] = nod;
    inceput[nod] = ordine[0];

    int cantitate = 1 , maxim = 0;
    for (int indice = 0 ; indice < (int)adiacenta[nod].size() ; indice++)
    {
        if (adiacenta[nod][indice].first == sursa)
            { swap(adiacenta[nod][indice] , adiacenta[nod].back()); adiacenta[nod].pop_back(); indice--; continue; }

        adancime[adiacenta[nod][indice].first] = {adancime[nod].first + 1 , adancime[nod].second + adiacenta[nod][indice].second};
        const int termen = Precalculare(adiacenta[nod][indice].first , nod);
        if (termen > maxim)
            { swap(adiacenta[nod][indice] , adiacenta[nod][0]); maxim = termen; }

        cantitate += termen;
    }

    sfarsit[nod] = ordine[0];

    return cantitate;
}

void Solve (const int nod , const int dorit , const bool elimina)
{
    for (int indice = 1 ; indice < (int)adiacenta[nod].size() ; indice++)
        { Solve(adiacenta[nod][indice].first , dorit , true); }

    if (!adiacenta[nod].empty())
        { Solve(adiacenta[nod][0].first , dorit , false); }

    auto locatie = candidati.find(adancime[nod].second + dorit);
    if (locatie != candidati.end())
        { rezultat = min(rezultat , locatie -> second - adancime[nod].first); }

    candidati[adancime[nod].second] = adancime[nod].first;
    for (int indice = 1 ; indice < (int)adiacenta[nod].size() ; indice++)
    {
        int& vecin = adiacenta[nod][indice].first;
        for (int __indice = inceput[vecin] ; __indice <= sfarsit[vecin] ; __indice++)
        {
            int& __nod = ordine[__indice];
            const pair <int , int64_t> termen = {adancime[__nod].first - adancime[nod].first , adancime[__nod].second - adancime[nod].second};
            locatie = candidati.find(dorit - termen.second + adancime[nod].second);
            if (locatie != candidati.end())
                { rezultat = min(rezultat , termen.first + locatie -> second - adancime[nod].first); }
        }
        
        for (int __indice = inceput[vecin] ; __indice <= sfarsit[vecin] ; __indice++)
        {
            int& __nod = ordine[__indice];
            locatie = candidati.find(adancime[__nod].second);
            if (locatie != candidati.end())
                { locatie -> second = min(locatie -> second , adancime[__nod].first); }
            else
                { candidati[adancime[__nod].second] = adancime[__nod].first; }
        }
    }

    if (elimina) 
        { candidati.clear(); }
}

int best_path (int numar_noduri , int dorit , int muchii[][2] , int cost[])
{
    for (int indice = 0 ; indice < numar_noduri - 1 ; indice++)
    {
        adiacenta[muchii[indice][0]].emplace_back(muchii[indice][1] , cost[indice]);
        adiacenta[muchii[indice][1]].emplace_back(muchii[indice][0] , cost[indice]);
    }

    Precalculare(0 , -1);
    Solve(0 , dorit , false);

    if (rezultat == INT32_MAX)
        { rezultat = -1; }

    return rezultat;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57