Submission #990548

#	Time	Username	Problem	Language	Result	Execution time	Memory
990548		ivaziva	Race (IOI11_race)	C++14	0 / 100	3068 ms	10332 KiB

race

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

using namespace std;

#define MAXN 200010

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

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

long long get_centroid(long long node,long long pret,long long velicina)
{
    long long s=adj[node].size();
    for (long long i=0;i<s;i++)
    {
        long long 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(long long node,long long pret,long long stanje,long long dubina,long long depth)
{
    if (dubina>k) return;
    if (stanje==false)
    {
        long long 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);
    }
    long long s=adj[node].size();
    for (long long i=0;i<s;i++)
    {
        long long sled=adj[node][i].first;
        long long tezina=adj[node][i].second;
        if (uklonjeno[sled]==true) continue;
        racunamo(sled,node,stanje,dubina+tezina,depth+1);
    }
}

void centroid_decomposition(long long node)
{
    subtree_size(node,-1);
    long long centroida=get_centroid(node,-1,siz[node]);
    uklonjeno[centroida]=true;
    long long s=adj[centroida].size();
    for (long long i=0;i<s;i++)
    {
        long long sled=adj[centroida][i].first;
        long long 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 (long long i=0;i<s;i++)
    {
        long long 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 (long long i=0;i<n-1;i++)
    {
        long long a=H[i][0],b=H[i][1];
        long long len=L[i];
        adj[a].push_back({b,len});
        adj[b].push_back({a,len});
    }
    centroid_decomposition(0);
    if (ans==LLONG_MAX) return -1;
    else return (int)ans;
};

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