oj.uz

Submission #990548

# Submission time Handle Problem Language Result Execution time Memory
990548 2024-05-30T15:52:50 Z ivaziva Race (IOI11_race) C++14
0 / 100
 3000 ms 10332 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3068 ms 10332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3068 ms 10332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3068 ms 10332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3068 ms 10332 KB Time limit exceeded
2 Halted 0 ms 0 KB -