Submission #426075

#	Time	Username	Problem	Language	Result	Execution time	Memory
426075		JeanBombeur	Race (IOI11_race)	C++17	100 / 100	583 ms	46772 KiB

race

#include <cstdio>
#include <iostream>
#include <vector>
#include "race.h"
using namespace std;

const int INFINI = (1000 * 1000 * 1000);
const int MAX_NOEUDS = (200 * 1000);
const int DIST_MAX = (1000 * 1000);

vector <pair <int, int>> Voisins[MAX_NOEUDS];

pair <pair <int, int>, pair <int, int>> DistancesMin[DIST_MAX];

vector <int> Update;

bool Traite[MAX_NOEUDS];

int NbFils[MAX_NOEUDS];

int cible;

void Init() {
    for (int i = 0; i < DIST_MAX; i ++)
    {
        DistancesMin[i].first = DistancesMin[i].second = {INFINI, -1};
    }
    return;
}

int Count(int noeud, int pere) {
    int sum = 1;
    for (pair <int, int> dest : Voisins[noeud])
    {
        if (!Traite[dest.first] && dest.first != pere)
            sum += Count(dest.first, noeud);
    }
    return NbFils[noeud] = sum;
}

int FindCentroide(int noeud, int pere, int borne) {
    for (pair <int, int> dest : Voisins[noeud])
    {
        if (!Traite[dest.first] && dest.first != pere && NbFils[dest.first] > borne)
            return FindCentroide(dest.first, noeud, borne);
    }
    return noeud;
}

void Explore(int noeud, int pere, int dist, int prof, int compo) {
    if (dist > cible)
        return;
    Update.push_back(dist);
    if (prof < DistancesMin[dist].first.first)
    {
        if (compo != DistancesMin[dist].first.second)
            DistancesMin[dist].second = DistancesMin[dist].first;
        DistancesMin[dist].first = {prof, compo};
    }
    else if (prof < DistancesMin[dist].second.first && compo != DistancesMin[dist].first.second)
        DistancesMin[dist].second = {prof, compo};
    for (pair <int, int> dest : Voisins[noeud])
    {
        if (!Traite[dest.first] && dest.first != pere)
            Explore(dest.first, noeud, dist + dest.second, prof + 1, compo);
    }
    return;
}

int TraiteCentroide(int noeud) {
    int nb = 0;
    DistancesMin[0].first = {0, -1};
    for (pair <int, int> dest : Voisins[noeud])
    {
        if (!Traite[dest.first])
        {
            Explore(dest.first, noeud, dest.second, 1, nb ++);
        }
    }
    int ans = INFINI;
    for (int a : Update)
    {
        if (DistancesMin[a].first.second != DistancesMin[cible - a].first.second)
            ans = min(ans, DistancesMin[a].first.first + DistancesMin[cible - a].first.first);
        else
        {
            ans = min(ans, DistancesMin[a].first.first + DistancesMin[cible - a].second.first);
            ans = min(ans, DistancesMin[a].second.first + DistancesMin[cible - a].first.first);
        }
    }
    for (int a : Update)
    {
        DistancesMin[a].first = DistancesMin[a].second = {INFINI, -1};
    }
    Update.clear();
    Traite[noeud] = true;
    for (pair <int, int> dest : Voisins[noeud])
    {
        if (!Traite[dest.first])
        {
            Count(dest.first, noeud);
            ans = min(ans, TraiteCentroide(FindCentroide(dest.first, noeud, NbFils[dest.first] / 2)));
        }
    }
    return ans;
}

int best_path(int nbSommets, int target, int Aretes[][2], int Poids[]) {
    for (int i = 0; i < nbSommets - 1; i ++)
    {
        Voisins[Aretes[i][0]].push_back({Aretes[i][1], Poids[i]});
        Voisins[Aretes[i][1]].push_back({Aretes[i][0], Poids[i]});
    }
    cible = target;
    Init();
    Count(0, -1);
    int r = TraiteCentroide(FindCentroide(0, -1, NbFils[0] / 2));
    if (r == INFINI)
        r = -1;
    return r;
}

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