Submission #990552

#	Time	Username	Problem	Language	Result	Execution time	Memory
990552		ivaziva	Race (IOI11_race)	C++14	0 / 100	3032 ms	9560 KiB

race

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

using namespace std;

#define MAXN 200010

int n,k;
vector<pair<int,int>> adj[MAXN];
int siz[MAXN];
bool uklonjeno[MAXN];
map<int,int> mapa;
int ans=INT_MAX;

int subtree_size(int node,int pret)
{
    siz[node]=1;
    int s=adj[node].size();
    for (int i=0;i<s;i++)
    {
        int sled=adj[node][i].first;
        if (sled==pret) continue;
        if (uklonjeno[sled]==true) continue;
        siz[node]+=subtree_size(sled,node);
    }
    return siz[node];
}

int get_centroid(int node,int pret,int velicina)
{
    int s=adj[node].size();
    for (int i=0;i<s;i++)
    {
        int sled=adj[node][i].first;
        if (sled==pret) continue;
        if (uklonjeno[sled]==true) continue;
        if (siz[sled]*2>velicina) return get_centroid(sled,node,velicina);
    }
    return node;
}

void racunamo(int node,int pret,bool stanje,int dubina,int depth)
{
    if (dubina>k) return;
    if (stanje==false)
    {
        int val=k-dubina;
        if (mapa.find(val)!=mapa.end()) ans=min(ans,depth+mapa[val]);
    }
    else
    {
        if (mapa.find(dubina)==mapa.end()) mapa[dubina]=depth;
        else mapa[dubina]=min(mapa[dubina],depth);
    }
    int s=adj[node].size();
    for (int i=0;i<s;i++)
    {
        int sled=adj[node][i].first;
        int tezina=adj[node][i].second;
        if (uklonjeno[sled]==true) continue;
        racunamo(sled,node,stanje,dubina+tezina,depth+1);
    }
}

void centroid_decomposition(int node)
{
    subtree_size(node,-1);
    int centroida=get_centroid(node,-1,siz[node]);
    uklonjeno[centroida]=true;
    int s=adj[centroida].size();
    for (int i=0;i<s;i++)
    {
        int sled=adj[centroida][i].first;
        int tezina=adj[centroida][i].second;
        if (uklonjeno[sled]==true) continue;
        racunamo(sled,centroida,false,tezina,1);
        racunamo(sled,centroida,true,tezina,1);
    }
    if (mapa.find(k)!=mapa.end()) ans=min(ans,mapa[k]);
    mapa.clear();
    for (int i=0;i<s;i++)
    {
        int sled=adj[centroida][i].first;
        if (uklonjeno[sled]==true) continue;
        centroid_decomposition(sled);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    n=N,k=K;
    for (int i=0;i<n-1;i++)
    {
        int a=H[i][0],b=H[i][1];
        int len=L[i];
        adj[a].push_back({b,len});
        adj[b].push_back({a,len});
    }
    centroid_decomposition(0);
    if (ans==INT_MAX) return -1;
    else return ans;
};

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