Submission #970294

#	Time	Username	Problem	Language	Result	Execution time	Memory
970294		tset	Race (IOI11_race)	C++14	43 / 100	3061 ms	41424 KiB

race

#include "race.h"
#include<bits/stdc++.h>

using namespace std;

const int INF = 1e9+42;

#define pii pair<int, int>

int nbNodes, requestedSum;
vector<vector<pii>> voisinDe;
vector<int> profSubtree;
vector<bool> interdit;

int lenSubTree;

int dfs(int nde, int ansc)
{
    int ans = 1;
    for(pii iV : voisinDe[nde])
    {
        if(!interdit[iV.first] && iV.first != ansc)
        {
            ans += dfs(iV.first, nde);
        }
    }
    profSubtree[nde] = ans;
    return ans;
}
int getCentroid(int nde, int ansc)
{
    for(pii iV : voisinDe[nde])
    {
        if(!interdit[iV.first] && iV.first!= ansc)
        {
            if(profSubtree[iV.first] > (lenSubTree)/2)
            {
                return getCentroid(iV.first, nde);
            }
        }
    }
    return nde;
}

vector<pii> minDistToLen;
vector<pii> toUpd;//sum, len;

int timer;

int findLenghts(int nde, int ansc, int sum, int len)
{
    int ans = INF;
    if(sum > requestedSum)
        return INF;
    if(sum == requestedSum)
        return len;
    toUpd.push_back({sum, len});

    int sumRemain = requestedSum - sum;
    if(minDistToLen[sumRemain].first == timer)
        ans = len + minDistToLen[sumRemain].second;
    for(pii iV : voisinDe[nde])
    {
        if(!interdit[iV.first] && iV.first != ansc)
        {
            ans = min(ans, findLenghts(iV.first, nde, sum + iV.second, len+1));
        }
    }
    return ans;
}
int findMinPath(int nde)
{
    //printf("[centroid : %d]", nde);
    int ans = INF;
    for(pii iV : voisinDe[nde])
    {
        toUpd.clear();
        ans = min(findLenghts(iV.first, nde, iV.second, 1), ans);
        for(pii updAct : toUpd)
        {
            minDistToLen[updAct.first] = min(minDistToLen[updAct.first], {timer ,updAct.second});
        }
    }
    return ans;
} 

int best_path(int N, int K, int H[][2], int L[])
{
    nbNodes = N;
    requestedSum = K;
    profSubtree.resize(nbNodes);
    timer = 2*nbNodes;
    interdit.assign(nbNodes,  false);
    voisinDe.resize(nbNodes);
    minDistToLen.assign(1000042, {INF, INF});
    for(int i =0; i< nbNodes-1; i++)
    {
        voisinDe[H[i][0]].push_back({H[i][1], L[i]});
        voisinDe[H[i][1]].push_back({H[i][0], L[i]});
    }
    deque<int> process;
    lenSubTree = dfs(0, -1);
    int centroid = getCentroid(0, -1);
    process.push_back(centroid);
    int ansMin = INF;
    while (!process.empty())
    {
        int ndeToProcess = process.front();
        process.pop_front();
        interdit[ndeToProcess] = true;
        int ansAct=findMinPath(ndeToProcess);
        ansMin = min(ansMin, ansAct);
        timer--;
        for(pii iV : voisinDe[ndeToProcess])
        {
            if(!interdit[iV.first])
            {
                
                lenSubTree = dfs(iV.first, -1);
                centroid = getCentroid(iV.first, -1);
                process.push_back(centroid);
            }
        }
    }
    if(ansMin == INF)
        return -1;
    return ansMin;
}

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