#include<bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
template <typename T>
using matrix = vector<vector<T>>;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const double EPS = 1e-7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6+1;
int best_path(int n, int k, int h[][2], int l[]){
vector<int> check(n,0);
matrix<pii> grafo(n);
for(int i = 0; i < n-1; i++)
grafo[h[i][0]].push_back({h[i][1],l[i]}), grafo[h[i][1]].push_back({h[i][0],l[i]});
int centroid;
function<int(int,int,int)> dfsc = [&](int id, int last, int sizee){
int ret = 1, maxi = 0;
for(int i = 0; i < grafo[id].size(); i++){
pii viz = grafo[id][i];
if(viz.ff == last || check[viz.ff])
continue;
int cur = dfsc(viz.ff,id,sizee);
ret+=cur;
maxi = max(maxi,cur);
}
maxi = max(maxi,sizee-ret);
if(maxi <= sizee/2)
centroid = id;
return ret;
};
function<int(int,int,int,int,vector<pii>&v)> dfsd = [&](int id, int last, int ct, int dist, vector<pii>&v){
if(dist > 1e7)
dist = 1e7;
v.push_back({ct,dist});
int ret = 1;
for(int i = 0; i < grafo[id].size(); i++){
pii viz = grafo[id][i];
if(viz.ff == last || check[viz.ff])
continue;
ret+=dfsd(viz.ff,id,ct+1,dist+viz.ss,v);
}
return ret;
};
int resp = INF;
function<void(int,int)> findcentroid = [&](int id, int sizee){
dfsc(id,-1,sizee);
int curc = centroid;
check[curc] = 1;
map<int,int> m;
for(int i = 0; i < grafo[curc].size(); i++){
if(check[grafo[curc][i].ff])
continue;
vector<pii> dlist;
int subtree = dfsd(grafo[curc][i].ff,-1,1,grafo[curc][i].ss,dlist);
for(pii j : dlist){
if(m.count(k-j.ss))
resp = min(resp,m[k-j.ss]+j.ff);
}
for(pii j : dlist){
if(m.count(j.ss))
m[j.ss] = min(m[j.ss],j.ff);
else m[j.ss] = j.ff;
}
findcentroid(grafo[curc][i].ff,subtree);
}
if(m.count(k))
resp = min(resp,m[k]);
};
findcentroid(0,n);
if(resp == INF)
return -1;
return resp;
}
Compilation message
race.cpp: In lambda function:
race.cpp:30:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int i = 0; i < grafo[id].size(); i++){
| ~~^~~~~~~~~~~~~~~~~~
race.cpp: In lambda function:
race.cpp:48:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int i = 0; i < grafo[id].size(); i++){
| ~~^~~~~~~~~~~~~~~~~~
race.cpp: In lambda function:
race.cpp:65:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i = 0; i < grafo[curc].size(); i++){
| ~~^~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
300 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
300 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
304 KB |
Output is correct |
21 |
Correct |
2 ms |
332 KB |
Output is correct |
22 |
Correct |
3 ms |
436 KB |
Output is correct |
23 |
Correct |
3 ms |
440 KB |
Output is correct |
24 |
Correct |
3 ms |
460 KB |
Output is correct |
25 |
Correct |
2 ms |
460 KB |
Output is correct |
26 |
Correct |
2 ms |
332 KB |
Output is correct |
27 |
Correct |
2 ms |
332 KB |
Output is correct |
28 |
Correct |
2 ms |
460 KB |
Output is correct |
29 |
Correct |
2 ms |
332 KB |
Output is correct |
30 |
Correct |
2 ms |
444 KB |
Output is correct |
31 |
Correct |
3 ms |
332 KB |
Output is correct |
32 |
Correct |
2 ms |
460 KB |
Output is correct |
33 |
Correct |
3 ms |
460 KB |
Output is correct |
34 |
Correct |
2 ms |
460 KB |
Output is correct |
35 |
Correct |
2 ms |
460 KB |
Output is correct |
36 |
Correct |
2 ms |
460 KB |
Output is correct |
37 |
Correct |
2 ms |
460 KB |
Output is correct |
38 |
Correct |
2 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
300 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
330 ms |
10284 KB |
Output is correct |
20 |
Correct |
280 ms |
10060 KB |
Output is correct |
21 |
Correct |
313 ms |
10212 KB |
Output is correct |
22 |
Correct |
264 ms |
10172 KB |
Output is correct |
23 |
Correct |
421 ms |
10484 KB |
Output is correct |
24 |
Correct |
181 ms |
9928 KB |
Output is correct |
25 |
Correct |
259 ms |
16760 KB |
Output is correct |
26 |
Correct |
149 ms |
22296 KB |
Output is correct |
27 |
Correct |
371 ms |
18828 KB |
Output is correct |
28 |
Correct |
1046 ms |
62956 KB |
Output is correct |
29 |
Correct |
1025 ms |
61232 KB |
Output is correct |
30 |
Correct |
369 ms |
18832 KB |
Output is correct |
31 |
Correct |
361 ms |
18832 KB |
Output is correct |
32 |
Correct |
437 ms |
19072 KB |
Output is correct |
33 |
Correct |
608 ms |
19760 KB |
Output is correct |
34 |
Correct |
463 ms |
19896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
300 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
304 KB |
Output is correct |
21 |
Correct |
2 ms |
332 KB |
Output is correct |
22 |
Correct |
3 ms |
436 KB |
Output is correct |
23 |
Correct |
3 ms |
440 KB |
Output is correct |
24 |
Correct |
3 ms |
460 KB |
Output is correct |
25 |
Correct |
2 ms |
460 KB |
Output is correct |
26 |
Correct |
2 ms |
332 KB |
Output is correct |
27 |
Correct |
2 ms |
332 KB |
Output is correct |
28 |
Correct |
2 ms |
460 KB |
Output is correct |
29 |
Correct |
2 ms |
332 KB |
Output is correct |
30 |
Correct |
2 ms |
444 KB |
Output is correct |
31 |
Correct |
3 ms |
332 KB |
Output is correct |
32 |
Correct |
2 ms |
460 KB |
Output is correct |
33 |
Correct |
3 ms |
460 KB |
Output is correct |
34 |
Correct |
2 ms |
460 KB |
Output is correct |
35 |
Correct |
2 ms |
460 KB |
Output is correct |
36 |
Correct |
2 ms |
460 KB |
Output is correct |
37 |
Correct |
2 ms |
460 KB |
Output is correct |
38 |
Correct |
2 ms |
332 KB |
Output is correct |
39 |
Correct |
330 ms |
10284 KB |
Output is correct |
40 |
Correct |
280 ms |
10060 KB |
Output is correct |
41 |
Correct |
313 ms |
10212 KB |
Output is correct |
42 |
Correct |
264 ms |
10172 KB |
Output is correct |
43 |
Correct |
421 ms |
10484 KB |
Output is correct |
44 |
Correct |
181 ms |
9928 KB |
Output is correct |
45 |
Correct |
259 ms |
16760 KB |
Output is correct |
46 |
Correct |
149 ms |
22296 KB |
Output is correct |
47 |
Correct |
371 ms |
18828 KB |
Output is correct |
48 |
Correct |
1046 ms |
62956 KB |
Output is correct |
49 |
Correct |
1025 ms |
61232 KB |
Output is correct |
50 |
Correct |
369 ms |
18832 KB |
Output is correct |
51 |
Correct |
361 ms |
18832 KB |
Output is correct |
52 |
Correct |
437 ms |
19072 KB |
Output is correct |
53 |
Correct |
608 ms |
19760 KB |
Output is correct |
54 |
Correct |
463 ms |
19896 KB |
Output is correct |
55 |
Correct |
26 ms |
1684 KB |
Output is correct |
56 |
Correct |
16 ms |
1328 KB |
Output is correct |
57 |
Correct |
188 ms |
10120 KB |
Output is correct |
58 |
Correct |
58 ms |
9120 KB |
Output is correct |
59 |
Correct |
381 ms |
29256 KB |
Output is correct |
60 |
Correct |
1147 ms |
60304 KB |
Output is correct |
61 |
Correct |
437 ms |
20180 KB |
Output is correct |
62 |
Correct |
381 ms |
18840 KB |
Output is correct |
63 |
Correct |
413 ms |
18948 KB |
Output is correct |
64 |
Correct |
999 ms |
27980 KB |
Output is correct |
65 |
Correct |
901 ms |
30916 KB |
Output is correct |
66 |
Correct |
1036 ms |
46644 KB |
Output is correct |
67 |
Correct |
175 ms |
19380 KB |
Output is correct |
68 |
Correct |
558 ms |
27928 KB |
Output is correct |
69 |
Correct |
543 ms |
28504 KB |
Output is correct |
70 |
Correct |
495 ms |
26908 KB |
Output is correct |