#include <bits/stdc++.h>
using namespace std;
const int nmax=2e5+3;
vector <pair <int, int> > v[nmax];
map <int, int> m[nmax];
int k, ans=nmax;
void dfs(int nod, int parent, int d, int h)
{
m[nod][d]=h;
for(auto [i, cost]:v[nod])
{
if(i!=parent)
{
dfs(i, nod, d+cost, h+1);
if(m[i].size()>m[nod].size()) swap(m[i], m[nod]);
for(auto [dist, he]:m[i])
{
int caut=k+2*d-dist;
if(m[nod].count(caut))
{
ans=min(ans, he+m[nod][caut]-2*h);
}
}
for(auto [dist, he]:m[i])
{
if(m[nod].count(dist))
{
m[nod][dist]=min(m[nod][dist], he);
}
else m[nod][dist]=he;
}
}
}
}
long long best_path(int n, int k, int h[][2], int l[])
{
::k=k;
for(int i=0; i<n-1; i++)
{
int a=h[i][0], b=h[i][1];
v[a].push_back({b, l[i]});
v[b].push_back({a, l[i]});
}
dfs(0, -1, 0, 1);
if(ans==nmax) return -1;
return ans;
}
Compilation message
race.cpp: In function 'void dfs(int, int, int, int)':
race.cpp:12:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
12 | for(auto [i, cost]:v[nod])
| ^
race.cpp:18:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
18 | for(auto [dist, he]:m[i])
| ^
race.cpp:26:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
26 | for(auto [dist, he]:m[i])
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 2 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 3 |
Correct |
7 ms |
14580 KB |
Output is correct |
| 4 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 5 |
Correct |
7 ms |
14416 KB |
Output is correct |
| 6 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 7 |
Correct |
6 ms |
14404 KB |
Output is correct |
| 8 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 9 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 10 |
Correct |
6 ms |
14488 KB |
Output is correct |
| 11 |
Correct |
6 ms |
14512 KB |
Output is correct |
| 12 |
Correct |
7 ms |
14428 KB |
Output is correct |
| 13 |
Correct |
7 ms |
14620 KB |
Output is correct |
| 14 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 15 |
Correct |
6 ms |
14568 KB |
Output is correct |
| 16 |
Correct |
6 ms |
14540 KB |
Output is correct |
| 17 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 18 |
Correct |
6 ms |
14428 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 2 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 3 |
Correct |
7 ms |
14580 KB |
Output is correct |
| 4 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 5 |
Correct |
7 ms |
14416 KB |
Output is correct |
| 6 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 7 |
Correct |
6 ms |
14404 KB |
Output is correct |
| 8 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 9 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 10 |
Correct |
6 ms |
14488 KB |
Output is correct |
| 11 |
Correct |
6 ms |
14512 KB |
Output is correct |
| 12 |
Correct |
7 ms |
14428 KB |
Output is correct |
| 13 |
Correct |
7 ms |
14620 KB |
Output is correct |
| 14 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 15 |
Correct |
6 ms |
14568 KB |
Output is correct |
| 16 |
Correct |
6 ms |
14540 KB |
Output is correct |
| 17 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 18 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 19 |
Correct |
7 ms |
14428 KB |
Output is correct |
| 20 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 21 |
Correct |
7 ms |
14680 KB |
Output is correct |
| 22 |
Correct |
8 ms |
14684 KB |
Output is correct |
| 23 |
Correct |
8 ms |
14668 KB |
Output is correct |
| 24 |
Correct |
6 ms |
14684 KB |
Output is correct |
| 25 |
Correct |
7 ms |
14684 KB |
Output is correct |
| 26 |
Correct |
7 ms |
14684 KB |
Output is correct |
| 27 |
Correct |
9 ms |
14544 KB |
Output is correct |
| 28 |
Correct |
7 ms |
14684 KB |
Output is correct |
| 29 |
Correct |
7 ms |
14668 KB |
Output is correct |
| 30 |
Correct |
7 ms |
14684 KB |
Output is correct |
| 31 |
Correct |
8 ms |
14684 KB |
Output is correct |
| 32 |
Correct |
7 ms |
14736 KB |
Output is correct |
| 33 |
Correct |
7 ms |
14680 KB |
Output is correct |
| 34 |
Correct |
7 ms |
14736 KB |
Output is correct |
| 35 |
Correct |
6 ms |
14684 KB |
Output is correct |
| 36 |
Correct |
6 ms |
14684 KB |
Output is correct |
| 37 |
Correct |
6 ms |
14684 KB |
Output is correct |
| 38 |
Correct |
7 ms |
14684 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 2 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 3 |
Correct |
7 ms |
14580 KB |
Output is correct |
| 4 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 5 |
Correct |
7 ms |
14416 KB |
Output is correct |
| 6 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 7 |
Correct |
6 ms |
14404 KB |
Output is correct |
| 8 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 9 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 10 |
Correct |
6 ms |
14488 KB |
Output is correct |
| 11 |
Correct |
6 ms |
14512 KB |
Output is correct |
| 12 |
Correct |
7 ms |
14428 KB |
Output is correct |
| 13 |
Correct |
7 ms |
14620 KB |
Output is correct |
| 14 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 15 |
Correct |
6 ms |
14568 KB |
Output is correct |
| 16 |
Correct |
6 ms |
14540 KB |
Output is correct |
| 17 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 18 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 19 |
Correct |
84 ms |
32356 KB |
Output is correct |
| 20 |
Correct |
90 ms |
32344 KB |
Output is correct |
| 21 |
Correct |
83 ms |
32080 KB |
Output is correct |
| 22 |
Correct |
77 ms |
31972 KB |
Output is correct |
| 23 |
Correct |
108 ms |
41552 KB |
Output is correct |
| 24 |
Correct |
91 ms |
34392 KB |
Output is correct |
| 25 |
Correct |
65 ms |
33616 KB |
Output is correct |
| 26 |
Correct |
47 ms |
40532 KB |
Output is correct |
| 27 |
Correct |
142 ms |
41556 KB |
Output is correct |
| 28 |
Correct |
203 ms |
76168 KB |
Output is correct |
| 29 |
Correct |
210 ms |
74580 KB |
Output is correct |
| 30 |
Correct |
138 ms |
41528 KB |
Output is correct |
| 31 |
Correct |
142 ms |
41556 KB |
Output is correct |
| 32 |
Correct |
158 ms |
41608 KB |
Output is correct |
| 33 |
Correct |
167 ms |
45000 KB |
Output is correct |
| 34 |
Correct |
262 ms |
69900 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 2 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 3 |
Correct |
7 ms |
14580 KB |
Output is correct |
| 4 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 5 |
Correct |
7 ms |
14416 KB |
Output is correct |
| 6 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 7 |
Correct |
6 ms |
14404 KB |
Output is correct |
| 8 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 9 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 10 |
Correct |
6 ms |
14488 KB |
Output is correct |
| 11 |
Correct |
6 ms |
14512 KB |
Output is correct |
| 12 |
Correct |
7 ms |
14428 KB |
Output is correct |
| 13 |
Correct |
7 ms |
14620 KB |
Output is correct |
| 14 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 15 |
Correct |
6 ms |
14568 KB |
Output is correct |
| 16 |
Correct |
6 ms |
14540 KB |
Output is correct |
| 17 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 18 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 19 |
Correct |
7 ms |
14428 KB |
Output is correct |
| 20 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 21 |
Correct |
7 ms |
14680 KB |
Output is correct |
| 22 |
Correct |
8 ms |
14684 KB |
Output is correct |
| 23 |
Correct |
8 ms |
14668 KB |
Output is correct |
| 24 |
Correct |
6 ms |
14684 KB |
Output is correct |
| 25 |
Correct |
7 ms |
14684 KB |
Output is correct |
| 26 |
Correct |
7 ms |
14684 KB |
Output is correct |
| 27 |
Correct |
9 ms |
14544 KB |
Output is correct |
| 28 |
Correct |
7 ms |
14684 KB |
Output is correct |
| 29 |
Correct |
7 ms |
14668 KB |
Output is correct |
| 30 |
Correct |
7 ms |
14684 KB |
Output is correct |
| 31 |
Correct |
8 ms |
14684 KB |
Output is correct |
| 32 |
Correct |
7 ms |
14736 KB |
Output is correct |
| 33 |
Correct |
7 ms |
14680 KB |
Output is correct |
| 34 |
Correct |
7 ms |
14736 KB |
Output is correct |
| 35 |
Correct |
6 ms |
14684 KB |
Output is correct |
| 36 |
Correct |
6 ms |
14684 KB |
Output is correct |
| 37 |
Correct |
6 ms |
14684 KB |
Output is correct |
| 38 |
Correct |
7 ms |
14684 KB |
Output is correct |
| 39 |
Correct |
84 ms |
32356 KB |
Output is correct |
| 40 |
Correct |
90 ms |
32344 KB |
Output is correct |
| 41 |
Correct |
83 ms |
32080 KB |
Output is correct |
| 42 |
Correct |
77 ms |
31972 KB |
Output is correct |
| 43 |
Correct |
108 ms |
41552 KB |
Output is correct |
| 44 |
Correct |
91 ms |
34392 KB |
Output is correct |
| 45 |
Correct |
65 ms |
33616 KB |
Output is correct |
| 46 |
Correct |
47 ms |
40532 KB |
Output is correct |
| 47 |
Correct |
142 ms |
41556 KB |
Output is correct |
| 48 |
Correct |
203 ms |
76168 KB |
Output is correct |
| 49 |
Correct |
210 ms |
74580 KB |
Output is correct |
| 50 |
Correct |
138 ms |
41528 KB |
Output is correct |
| 51 |
Correct |
142 ms |
41556 KB |
Output is correct |
| 52 |
Correct |
158 ms |
41608 KB |
Output is correct |
| 53 |
Correct |
167 ms |
45000 KB |
Output is correct |
| 54 |
Correct |
262 ms |
69900 KB |
Output is correct |
| 55 |
Correct |
15 ms |
16960 KB |
Output is correct |
| 56 |
Correct |
10 ms |
15960 KB |
Output is correct |
| 57 |
Correct |
48 ms |
30288 KB |
Output is correct |
| 58 |
Correct |
39 ms |
25288 KB |
Output is correct |
| 59 |
Correct |
70 ms |
45140 KB |
Output is correct |
| 60 |
Correct |
193 ms |
74760 KB |
Output is correct |
| 61 |
Correct |
167 ms |
44112 KB |
Output is correct |
| 62 |
Correct |
128 ms |
41556 KB |
Output is correct |
| 63 |
Correct |
167 ms |
41812 KB |
Output is correct |
| 64 |
Correct |
329 ms |
82972 KB |
Output is correct |
| 65 |
Correct |
337 ms |
81916 KB |
Output is correct |
| 66 |
Correct |
223 ms |
70992 KB |
Output is correct |
| 67 |
Correct |
112 ms |
37564 KB |
Output is correct |
| 68 |
Correct |
245 ms |
54612 KB |
Output is correct |
| 69 |
Correct |
288 ms |
58452 KB |
Output is correct |
| 70 |
Correct |
249 ms |
52820 KB |
Output is correct |
