이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
};
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |