#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
const int MAXK = 1e6;
const int INF = 987654321;
int N, K, ans=987654321;
vector<pii> adj[MAXN+10];
int sz[MAXN+10];
bool del[MAXN+10];
int M[MAXK+10];
void getsz(int now, int bef)
{
sz[now]=1;
for(pii nxt : adj[now])
{
if(del[nxt.first]) continue;
if(nxt.first==bef) continue;
getsz(nxt.first, now);
sz[now]+=sz[nxt.first];
}
}
int getcen(int now, int bef, int tot)
{
for(pii nxt : adj[now])
{
if(del[nxt.first]) continue;
if(nxt.first==bef) continue;
if(tot/2<sz[nxt.first]) return getcen(nxt.first, now, tot);
}
return now;
}
void dfs(int now, int bef, int dep, int len, vector<pii>& V)
{
V.push_back({len, dep});
for(pii nxt : adj[now])
{
if(del[nxt.first]) continue;
if(nxt.first==bef) continue;
if(len+nxt.second>K) continue;
dfs(nxt.first, now, dep+1, len+nxt.second, V);
}
}
void decomp(int now)
{
int i, j;
getsz(now, now);
now=getcen(now, now, sz[now]);
del[now]=true;
vector<int> change;
change.push_back(0);
M[0]=0;
for(pii nxt : adj[now])
{
if(del[nxt.first]) continue;
vector<pii> V;
dfs(nxt.first, nxt.first, 1, nxt.second, V);
for(i=0; i<V.size(); i++)
{
int len=V[i].first, dep=V[i].second;
if(len>K) continue;
change.push_back(len);
ans=min(ans, M[K-len]+dep);
}
for(i=0; i<V.size(); i++)
{
int len=V[i].first, dep=V[i].second;
if(len>K) continue;
M[len]=min(M[len], dep);
}
}
for(i=0; i<change.size(); i++) M[change[i]]=INF;
for(pii nxt : adj[now])
{
if(del[nxt.first]) continue;
decomp(nxt.first);
}
}
int best_path(int NN, int KK, int HH[][2], int LL[])
{
int i, j;
N=NN; K=KK;
for(i=0; i+1<N; i++)
{
int u=HH[i][0], v=HH[i][1], w=LL[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
for(i=0; i<=1000000; i++) M[i]=INF;
decomp(0);
if(ans==INF) ans=-1;
return ans;
}
Compilation message
race.cpp: In function 'void decomp(int)':
race.cpp:72:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<V.size(); i++)
~^~~~~~~~~
race.cpp:80:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<V.size(); i++)
~^~~~~~~~~
race.cpp:88:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<change.size(); i++) M[change[i]]=INF;
~^~~~~~~~~~~~~~
race.cpp:58:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:99:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
8952 KB |
Output is correct |
2 |
Correct |
10 ms |
8952 KB |
Output is correct |
3 |
Correct |
10 ms |
8952 KB |
Output is correct |
4 |
Correct |
10 ms |
8924 KB |
Output is correct |
5 |
Correct |
10 ms |
8952 KB |
Output is correct |
6 |
Correct |
10 ms |
8952 KB |
Output is correct |
7 |
Correct |
10 ms |
8952 KB |
Output is correct |
8 |
Correct |
10 ms |
8952 KB |
Output is correct |
9 |
Correct |
10 ms |
8924 KB |
Output is correct |
10 |
Correct |
10 ms |
8952 KB |
Output is correct |
11 |
Correct |
10 ms |
8952 KB |
Output is correct |
12 |
Correct |
10 ms |
8952 KB |
Output is correct |
13 |
Correct |
10 ms |
8952 KB |
Output is correct |
14 |
Correct |
10 ms |
8952 KB |
Output is correct |
15 |
Correct |
10 ms |
8952 KB |
Output is correct |
16 |
Correct |
10 ms |
8952 KB |
Output is correct |
17 |
Correct |
10 ms |
8952 KB |
Output is correct |
18 |
Correct |
10 ms |
8952 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
8952 KB |
Output is correct |
2 |
Correct |
10 ms |
8952 KB |
Output is correct |
3 |
Correct |
10 ms |
8952 KB |
Output is correct |
4 |
Correct |
10 ms |
8924 KB |
Output is correct |
5 |
Correct |
10 ms |
8952 KB |
Output is correct |
6 |
Correct |
10 ms |
8952 KB |
Output is correct |
7 |
Correct |
10 ms |
8952 KB |
Output is correct |
8 |
Correct |
10 ms |
8952 KB |
Output is correct |
9 |
Correct |
10 ms |
8924 KB |
Output is correct |
10 |
Correct |
10 ms |
8952 KB |
Output is correct |
11 |
Correct |
10 ms |
8952 KB |
Output is correct |
12 |
Correct |
10 ms |
8952 KB |
Output is correct |
13 |
Correct |
10 ms |
8952 KB |
Output is correct |
14 |
Correct |
10 ms |
8952 KB |
Output is correct |
15 |
Correct |
10 ms |
8952 KB |
Output is correct |
16 |
Correct |
10 ms |
8952 KB |
Output is correct |
17 |
Correct |
10 ms |
8952 KB |
Output is correct |
18 |
Correct |
10 ms |
8952 KB |
Output is correct |
19 |
Correct |
10 ms |
9080 KB |
Output is correct |
20 |
Correct |
10 ms |
8952 KB |
Output is correct |
21 |
Correct |
13 ms |
8980 KB |
Output is correct |
22 |
Correct |
13 ms |
8952 KB |
Output is correct |
23 |
Correct |
10 ms |
8952 KB |
Output is correct |
24 |
Correct |
11 ms |
9080 KB |
Output is correct |
25 |
Correct |
14 ms |
8952 KB |
Output is correct |
26 |
Correct |
11 ms |
9080 KB |
Output is correct |
27 |
Correct |
10 ms |
9080 KB |
Output is correct |
28 |
Correct |
11 ms |
9080 KB |
Output is correct |
29 |
Correct |
11 ms |
8952 KB |
Output is correct |
30 |
Correct |
11 ms |
9080 KB |
Output is correct |
31 |
Correct |
11 ms |
9080 KB |
Output is correct |
32 |
Correct |
11 ms |
9080 KB |
Output is correct |
33 |
Correct |
11 ms |
9080 KB |
Output is correct |
34 |
Correct |
11 ms |
9072 KB |
Output is correct |
35 |
Correct |
11 ms |
8952 KB |
Output is correct |
36 |
Correct |
11 ms |
9080 KB |
Output is correct |
37 |
Correct |
11 ms |
9080 KB |
Output is correct |
38 |
Correct |
11 ms |
8952 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
8952 KB |
Output is correct |
2 |
Correct |
10 ms |
8952 KB |
Output is correct |
3 |
Correct |
10 ms |
8952 KB |
Output is correct |
4 |
Correct |
10 ms |
8924 KB |
Output is correct |
5 |
Correct |
10 ms |
8952 KB |
Output is correct |
6 |
Correct |
10 ms |
8952 KB |
Output is correct |
7 |
Correct |
10 ms |
8952 KB |
Output is correct |
8 |
Correct |
10 ms |
8952 KB |
Output is correct |
9 |
Correct |
10 ms |
8924 KB |
Output is correct |
10 |
Correct |
10 ms |
8952 KB |
Output is correct |
11 |
Correct |
10 ms |
8952 KB |
Output is correct |
12 |
Correct |
10 ms |
8952 KB |
Output is correct |
13 |
Correct |
10 ms |
8952 KB |
Output is correct |
14 |
Correct |
10 ms |
8952 KB |
Output is correct |
15 |
Correct |
10 ms |
8952 KB |
Output is correct |
16 |
Correct |
10 ms |
8952 KB |
Output is correct |
17 |
Correct |
10 ms |
8952 KB |
Output is correct |
18 |
Correct |
10 ms |
8952 KB |
Output is correct |
19 |
Correct |
206 ms |
16000 KB |
Output is correct |
20 |
Correct |
184 ms |
15736 KB |
Output is correct |
21 |
Correct |
178 ms |
16284 KB |
Output is correct |
22 |
Correct |
175 ms |
16616 KB |
Output is correct |
23 |
Correct |
136 ms |
16120 KB |
Output is correct |
24 |
Correct |
98 ms |
15900 KB |
Output is correct |
25 |
Correct |
193 ms |
18652 KB |
Output is correct |
26 |
Correct |
157 ms |
23004 KB |
Output is correct |
27 |
Correct |
248 ms |
22852 KB |
Output is correct |
28 |
Correct |
396 ms |
34040 KB |
Output is correct |
29 |
Correct |
426 ms |
33272 KB |
Output is correct |
30 |
Correct |
259 ms |
22816 KB |
Output is correct |
31 |
Correct |
253 ms |
22876 KB |
Output is correct |
32 |
Correct |
338 ms |
22908 KB |
Output is correct |
33 |
Correct |
394 ms |
21696 KB |
Output is correct |
34 |
Correct |
319 ms |
22524 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
8952 KB |
Output is correct |
2 |
Correct |
10 ms |
8952 KB |
Output is correct |
3 |
Correct |
10 ms |
8952 KB |
Output is correct |
4 |
Correct |
10 ms |
8924 KB |
Output is correct |
5 |
Correct |
10 ms |
8952 KB |
Output is correct |
6 |
Correct |
10 ms |
8952 KB |
Output is correct |
7 |
Correct |
10 ms |
8952 KB |
Output is correct |
8 |
Correct |
10 ms |
8952 KB |
Output is correct |
9 |
Correct |
10 ms |
8924 KB |
Output is correct |
10 |
Correct |
10 ms |
8952 KB |
Output is correct |
11 |
Correct |
10 ms |
8952 KB |
Output is correct |
12 |
Correct |
10 ms |
8952 KB |
Output is correct |
13 |
Correct |
10 ms |
8952 KB |
Output is correct |
14 |
Correct |
10 ms |
8952 KB |
Output is correct |
15 |
Correct |
10 ms |
8952 KB |
Output is correct |
16 |
Correct |
10 ms |
8952 KB |
Output is correct |
17 |
Correct |
10 ms |
8952 KB |
Output is correct |
18 |
Correct |
10 ms |
8952 KB |
Output is correct |
19 |
Correct |
10 ms |
9080 KB |
Output is correct |
20 |
Correct |
10 ms |
8952 KB |
Output is correct |
21 |
Correct |
13 ms |
8980 KB |
Output is correct |
22 |
Correct |
13 ms |
8952 KB |
Output is correct |
23 |
Correct |
10 ms |
8952 KB |
Output is correct |
24 |
Correct |
11 ms |
9080 KB |
Output is correct |
25 |
Correct |
14 ms |
8952 KB |
Output is correct |
26 |
Correct |
11 ms |
9080 KB |
Output is correct |
27 |
Correct |
10 ms |
9080 KB |
Output is correct |
28 |
Correct |
11 ms |
9080 KB |
Output is correct |
29 |
Correct |
11 ms |
8952 KB |
Output is correct |
30 |
Correct |
11 ms |
9080 KB |
Output is correct |
31 |
Correct |
11 ms |
9080 KB |
Output is correct |
32 |
Correct |
11 ms |
9080 KB |
Output is correct |
33 |
Correct |
11 ms |
9080 KB |
Output is correct |
34 |
Correct |
11 ms |
9072 KB |
Output is correct |
35 |
Correct |
11 ms |
8952 KB |
Output is correct |
36 |
Correct |
11 ms |
9080 KB |
Output is correct |
37 |
Correct |
11 ms |
9080 KB |
Output is correct |
38 |
Correct |
11 ms |
8952 KB |
Output is correct |
39 |
Correct |
206 ms |
16000 KB |
Output is correct |
40 |
Correct |
184 ms |
15736 KB |
Output is correct |
41 |
Correct |
178 ms |
16284 KB |
Output is correct |
42 |
Correct |
175 ms |
16616 KB |
Output is correct |
43 |
Correct |
136 ms |
16120 KB |
Output is correct |
44 |
Correct |
98 ms |
15900 KB |
Output is correct |
45 |
Correct |
193 ms |
18652 KB |
Output is correct |
46 |
Correct |
157 ms |
23004 KB |
Output is correct |
47 |
Correct |
248 ms |
22852 KB |
Output is correct |
48 |
Correct |
396 ms |
34040 KB |
Output is correct |
49 |
Correct |
426 ms |
33272 KB |
Output is correct |
50 |
Correct |
259 ms |
22816 KB |
Output is correct |
51 |
Correct |
253 ms |
22876 KB |
Output is correct |
52 |
Correct |
338 ms |
22908 KB |
Output is correct |
53 |
Correct |
394 ms |
21696 KB |
Output is correct |
54 |
Correct |
319 ms |
22524 KB |
Output is correct |
55 |
Correct |
22 ms |
9720 KB |
Output is correct |
56 |
Correct |
22 ms |
9720 KB |
Output is correct |
57 |
Correct |
131 ms |
17004 KB |
Output is correct |
58 |
Correct |
56 ms |
16492 KB |
Output is correct |
59 |
Correct |
158 ms |
23004 KB |
Output is correct |
60 |
Correct |
682 ms |
36816 KB |
Output is correct |
61 |
Correct |
280 ms |
23288 KB |
Output is correct |
62 |
Correct |
336 ms |
23780 KB |
Output is correct |
63 |
Correct |
357 ms |
23780 KB |
Output is correct |
64 |
Correct |
533 ms |
25524 KB |
Output is correct |
65 |
Correct |
290 ms |
23672 KB |
Output is correct |
66 |
Correct |
548 ms |
31736 KB |
Output is correct |
67 |
Correct |
195 ms |
25508 KB |
Output is correct |
68 |
Correct |
361 ms |
24676 KB |
Output is correct |
69 |
Correct |
352 ms |
24936 KB |
Output is correct |
70 |
Correct |
331 ms |
24292 KB |
Output is correct |