This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "race.h"
using namespace std;
const int mxN = 2e5 + 3;
vector<pair<int, int>>G[mxN];
long long depth[mxN], length[mxN];
vector<int>visited;
int K;
void dfs(int node, int par){
for(pair<int, int>& v : G[node]){
if(v.first != par){
depth[v.first] = depth[node] + 1;
length[v.first] = length[node] + v.second;
visited.push_back(v.first);
if(length[v.first] > K)continue;
dfs(v.first, node);
}
}
}
int best_path(int n, int k, int H[][2], int L[]){
K = k;
for(int i = 0;i < n - 1;++i){
int u = H[i][0], v = H[i][1];
G[u].push_back({v, L[i]});
G[v].push_back({u, L[i]});
}
long long mn = 1e18;
for(int i = 0;i < n;++i){
dfs(i, i);
for(int &j : visited){
if(length[j] == k){
mn = min(mn, depth[j]);
}
}
for(int &j : visited){
depth[j] = 0;
length[j] = 0;
}
visited.clear();
}
if(mn == 1e18)return -1;
return mn;
}
// int main()
// {
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// int n;
// cin >> n >> K;
// int H[n - 1][2], L[n - 1];
// for(int i = 0;i < n - 1;++i){
// cin >> H[i][0] >> H[i][1] >> L[i];
// }
// cout << best_path(n, K, H, L);
// }
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/
# | 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... |