이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ll long long
#define ull unsigned ll
#include "race.h"
using namespace std;
constexpr int debug = 1;
constexpr int M = 2e5+7;
constexpr int D = 1e6+7;
int tree_size[M];
int total_size;
bool was_centroid[M];
ll Kek;
ll mini = 1e9+7;
ll closest[D];
queue<int> changes; //komorki z closest do wyzerowania
vector<pair<ll,ll>> adj[M];
inline void addEdge(ll a, ll b, ll val){
adj[a].pb({b, val});
adj[b].pb({a, val});
}
void set_size(int s, int p){
tree_size[s] = 1;
for(auto k: adj[s]){
if(k.F == p || was_centroid[k.F]) continue;
set_size(k.F, s);
tree_size[s] += tree_size[k.F];
}
}
int find_centroid(int s, int p){
for(auto k: adj[s]){
if(was_centroid[k.F]) continue;
else if(k.F == p){
if(total_size-tree_size[s] > total_size/2) return find_centroid(k.F, s);
}
else if(tree_size[k.F] > total_size/2){
return find_centroid(k.F, s);
}
}
return s;
}
void DFS1(int s, int p, ll dist_v, ll dist_e){ //sprawdza, ile ma odpowiadajacy wierzcholek
if(dist_e == Kek) mini = min(mini, dist_v+1);
if((dist_e < Kek) && (closest[Kek-dist_e])) mini = min(mini, closest[Kek-dist_e]+dist_v);
for(auto k: adj[s]){
if(was_centroid[k.F] || k.F == p) continue;
DFS1(k.F, s, dist_v+1, dist_e+k.S);
}
}
void DFS2(int s, int p, ll dist_v, ll dist_e){ //aktualizacje wierzcholkow w danych odleglosciach
if(dist_e <= Kek && dist_e != 0){
if(closest[dist_e] == 0 || closest[dist_e] > dist_v){
changes.push(dist_e);
closest[dist_e] = dist_v;
}
}
for(auto k: adj[s]){
if(was_centroid[k.F] || k.F == p) continue;
DFS2(k.F, s, dist_v+1, dist_e+k.S);
}
}
void centroid_decomposition(int x){
set_size(x, x);
total_size = tree_size[x];
int cen = find_centroid(x, x);
//robi cos na centroidzie
for(auto k: adj[cen]){
if(!was_centroid[k.F]){
DFS1(k.F, cen, 1, k.S);
DFS2(k.F, cen, 1, k.S);
}
}
while(!changes.empty()){
closest[changes.front()] = 0;
changes.pop();
}
was_centroid[cen] = 1;
for(auto k: adj[cen]){
if(!was_centroid[k.F]) centroid_decomposition(k.F);
}
}
int best_path(int N, int K, int H[][2], int L[]){
Kek = K;
for(int i = 0; i < N-1; i++){
addEdge(H[i][0], H[i][1], L[i]);
}
centroid_decomposition(0);
if(mini == 1e9+7) mini = -1;
return mini;
}
# | 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... |