#include "race.h"
#include <bits/stdc++.h>
#define ll int
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
//#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>*/
template<class S,class T>
bool chmin(S &a,const T &b) {
return a>b?(a=b)==b:false;
}
template<class S,class T>
bool chmax(S &a,const T &b) {
return a<b?(a=b)==b:false;
}
const ll inf=1e9+7;
const ll M=1e6+7;
vector<pll> g(M);
ll n,k;
vector<vll> cen(M);
ll sz[M];
pll dp[M];
ll ans=inf;
bool f[M];
void dfs_sz(ll v,ll p){
sz[v]=1;
for(auto i : g[v]){
if(i.fr==p || f[i.fr]) continue;
dfs_sz(i.fr,v);
sz[v]+=sz[i.fr];
}
}
ll find_cen(ll v,ll p,ll x){
for(auto i : g[v]){
if(i.fr==p || f[i.fr]) continue;
if(sz[i.fr]>x/2)return find_cen(i.fr,v,x);
}
return v;
}
void calc(ll v,ll p){
pll x;
dp[v]={{0,0}};
for(auto y : g[v]){
ll i=y.fr,len=y.sc;
if(i==p || f[i])continue;
calc(i,v);
ll l=0,r=0;
for(ll j=0;j<dp[i].size();j++){
dp[i][j].fr+=len;
dp[i][j].sc++;
}
for(auto j : dp[i]){
ll low=lb(all(dp[v]),make_pair(k-j.fr,0))-dp[v].begin();
if(low<dp[v].size() && dp[v][low].fr==k-j.fr)chmin(ans,dp[v][low].sc+j.sc);
}
while(l<dp[i].size() || r<dp[v].size()){
if(l<dp[i].size() && r<dp[v].size()){
if(dp[i][l].fr==dp[v][r].fr){
x.pb({dp[i][l].fr,min(dp[i][l].sc,dp[v][r].sc)});
l++;
r++;
}else if(dp[i][l].fr<dp[v][r].fr){
x.pb(dp[i][l]);
l++;
}else {
x.pb(dp[v][r]);
r++;
}
}else if(l<dp[i].size()){
x.pb(dp[i][l]);
l++;
}else{
x.pb(dp[v][r]);
r++;
}
}
dp[v]=x;
x.clear();
while(dp[v].size() && dp[v].bc.fr>k)dp[v].pob;
}
}
void cen_dec(ll v,ll p){
dfs_sz(v,p);
ll c=find_cen(v,p,sz[v]);
f[c]=1;
calc(c,0);
for(auto i : g[c]){
if(f[i.fr]) continue;
cen_dec(i.fr,c);
}
}
int best_path(int N, int K, int h[][2], int l[]){
n=N,k=K;
ll i,j,a,b;
for(i=0;i<n-1;i++){
a=h[i][0],b=h[i][1];
a++;
b++;
g[a].pb({b,l[i]});
g[b].pb({a,l[i]});
}
cen_dec(1,0);
if(ans==inf)return -1;
return ans;
}
/*
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
2
*/
Compilation message
race.cpp: In function 'void calc(int, int)':
race.cpp:68:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(ll j=0;j<dp[i].size();j++){
| ~^~~~~~~~~~~~~
race.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | if(low<dp[v].size() && dp[v][low].fr==k-j.fr)chmin(ans,dp[v][low].sc+j.sc);
| ~~~^~~~~~~~~~~~~
race.cpp:76:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | while(l<dp[i].size() || r<dp[v].size()){
| ~^~~~~~~~~~~~~
race.cpp:76:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | while(l<dp[i].size() || r<dp[v].size()){
| ~^~~~~~~~~~~~~
race.cpp:77:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | if(l<dp[i].size() && r<dp[v].size()){
| ~^~~~~~~~~~~~~
race.cpp:77:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | if(l<dp[i].size() && r<dp[v].size()){
| ~^~~~~~~~~~~~~
race.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | }else if(l<dp[i].size()){
| ~^~~~~~~~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:114:10: warning: unused variable 'j' [-Wunused-variable]
114 | ll i,j,a,b;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
75944 KB |
Output is correct |
2 |
Correct |
17 ms |
76120 KB |
Output is correct |
3 |
Correct |
17 ms |
76120 KB |
Output is correct |
4 |
Correct |
17 ms |
76124 KB |
Output is correct |
5 |
Correct |
18 ms |
76112 KB |
Output is correct |
6 |
Correct |
19 ms |
76120 KB |
Output is correct |
7 |
Correct |
18 ms |
76124 KB |
Output is correct |
8 |
Correct |
18 ms |
76108 KB |
Output is correct |
9 |
Correct |
19 ms |
76120 KB |
Output is correct |
10 |
Correct |
17 ms |
76124 KB |
Output is correct |
11 |
Correct |
18 ms |
76124 KB |
Output is correct |
12 |
Correct |
18 ms |
76124 KB |
Output is correct |
13 |
Correct |
19 ms |
76120 KB |
Output is correct |
14 |
Correct |
19 ms |
76124 KB |
Output is correct |
15 |
Correct |
19 ms |
76176 KB |
Output is correct |
16 |
Correct |
21 ms |
76124 KB |
Output is correct |
17 |
Correct |
18 ms |
76076 KB |
Output is correct |
18 |
Correct |
18 ms |
76124 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
75944 KB |
Output is correct |
2 |
Correct |
17 ms |
76120 KB |
Output is correct |
3 |
Correct |
17 ms |
76120 KB |
Output is correct |
4 |
Correct |
17 ms |
76124 KB |
Output is correct |
5 |
Correct |
18 ms |
76112 KB |
Output is correct |
6 |
Correct |
19 ms |
76120 KB |
Output is correct |
7 |
Correct |
18 ms |
76124 KB |
Output is correct |
8 |
Correct |
18 ms |
76108 KB |
Output is correct |
9 |
Correct |
19 ms |
76120 KB |
Output is correct |
10 |
Correct |
17 ms |
76124 KB |
Output is correct |
11 |
Correct |
18 ms |
76124 KB |
Output is correct |
12 |
Correct |
18 ms |
76124 KB |
Output is correct |
13 |
Correct |
19 ms |
76120 KB |
Output is correct |
14 |
Correct |
19 ms |
76124 KB |
Output is correct |
15 |
Correct |
19 ms |
76176 KB |
Output is correct |
16 |
Correct |
21 ms |
76124 KB |
Output is correct |
17 |
Correct |
18 ms |
76076 KB |
Output is correct |
18 |
Correct |
18 ms |
76124 KB |
Output is correct |
19 |
Correct |
17 ms |
76120 KB |
Output is correct |
20 |
Correct |
17 ms |
75928 KB |
Output is correct |
21 |
Correct |
19 ms |
76112 KB |
Output is correct |
22 |
Correct |
20 ms |
76124 KB |
Output is correct |
23 |
Correct |
21 ms |
76124 KB |
Output is correct |
24 |
Correct |
18 ms |
76120 KB |
Output is correct |
25 |
Correct |
19 ms |
76124 KB |
Output is correct |
26 |
Correct |
19 ms |
76180 KB |
Output is correct |
27 |
Correct |
18 ms |
76120 KB |
Output is correct |
28 |
Correct |
19 ms |
76120 KB |
Output is correct |
29 |
Correct |
19 ms |
76120 KB |
Output is correct |
30 |
Correct |
19 ms |
76324 KB |
Output is correct |
31 |
Correct |
19 ms |
76120 KB |
Output is correct |
32 |
Correct |
19 ms |
76120 KB |
Output is correct |
33 |
Correct |
21 ms |
76120 KB |
Output is correct |
34 |
Correct |
19 ms |
76380 KB |
Output is correct |
35 |
Correct |
20 ms |
76380 KB |
Output is correct |
36 |
Correct |
20 ms |
76380 KB |
Output is correct |
37 |
Correct |
21 ms |
76888 KB |
Output is correct |
38 |
Correct |
19 ms |
76636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
75944 KB |
Output is correct |
2 |
Correct |
17 ms |
76120 KB |
Output is correct |
3 |
Correct |
17 ms |
76120 KB |
Output is correct |
4 |
Correct |
17 ms |
76124 KB |
Output is correct |
5 |
Correct |
18 ms |
76112 KB |
Output is correct |
6 |
Correct |
19 ms |
76120 KB |
Output is correct |
7 |
Correct |
18 ms |
76124 KB |
Output is correct |
8 |
Correct |
18 ms |
76108 KB |
Output is correct |
9 |
Correct |
19 ms |
76120 KB |
Output is correct |
10 |
Correct |
17 ms |
76124 KB |
Output is correct |
11 |
Correct |
18 ms |
76124 KB |
Output is correct |
12 |
Correct |
18 ms |
76124 KB |
Output is correct |
13 |
Correct |
19 ms |
76120 KB |
Output is correct |
14 |
Correct |
19 ms |
76124 KB |
Output is correct |
15 |
Correct |
19 ms |
76176 KB |
Output is correct |
16 |
Correct |
21 ms |
76124 KB |
Output is correct |
17 |
Correct |
18 ms |
76076 KB |
Output is correct |
18 |
Correct |
18 ms |
76124 KB |
Output is correct |
19 |
Correct |
252 ms |
89428 KB |
Output is correct |
20 |
Correct |
245 ms |
89424 KB |
Output is correct |
21 |
Correct |
228 ms |
88652 KB |
Output is correct |
22 |
Correct |
228 ms |
87632 KB |
Output is correct |
23 |
Correct |
218 ms |
86416 KB |
Output is correct |
24 |
Correct |
121 ms |
86356 KB |
Output is correct |
25 |
Correct |
765 ms |
177232 KB |
Output is correct |
26 |
Correct |
263 ms |
131996 KB |
Output is correct |
27 |
Correct |
327 ms |
107680 KB |
Output is correct |
28 |
Correct |
775 ms |
115572 KB |
Output is correct |
29 |
Correct |
696 ms |
115384 KB |
Output is correct |
30 |
Correct |
357 ms |
107860 KB |
Output is correct |
31 |
Correct |
354 ms |
108072 KB |
Output is correct |
32 |
Correct |
386 ms |
102224 KB |
Output is correct |
33 |
Correct |
1534 ms |
222484 KB |
Output is correct |
34 |
Correct |
377 ms |
93412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
75944 KB |
Output is correct |
2 |
Correct |
17 ms |
76120 KB |
Output is correct |
3 |
Correct |
17 ms |
76120 KB |
Output is correct |
4 |
Correct |
17 ms |
76124 KB |
Output is correct |
5 |
Correct |
18 ms |
76112 KB |
Output is correct |
6 |
Correct |
19 ms |
76120 KB |
Output is correct |
7 |
Correct |
18 ms |
76124 KB |
Output is correct |
8 |
Correct |
18 ms |
76108 KB |
Output is correct |
9 |
Correct |
19 ms |
76120 KB |
Output is correct |
10 |
Correct |
17 ms |
76124 KB |
Output is correct |
11 |
Correct |
18 ms |
76124 KB |
Output is correct |
12 |
Correct |
18 ms |
76124 KB |
Output is correct |
13 |
Correct |
19 ms |
76120 KB |
Output is correct |
14 |
Correct |
19 ms |
76124 KB |
Output is correct |
15 |
Correct |
19 ms |
76176 KB |
Output is correct |
16 |
Correct |
21 ms |
76124 KB |
Output is correct |
17 |
Correct |
18 ms |
76076 KB |
Output is correct |
18 |
Correct |
18 ms |
76124 KB |
Output is correct |
19 |
Correct |
17 ms |
76120 KB |
Output is correct |
20 |
Correct |
17 ms |
75928 KB |
Output is correct |
21 |
Correct |
19 ms |
76112 KB |
Output is correct |
22 |
Correct |
20 ms |
76124 KB |
Output is correct |
23 |
Correct |
21 ms |
76124 KB |
Output is correct |
24 |
Correct |
18 ms |
76120 KB |
Output is correct |
25 |
Correct |
19 ms |
76124 KB |
Output is correct |
26 |
Correct |
19 ms |
76180 KB |
Output is correct |
27 |
Correct |
18 ms |
76120 KB |
Output is correct |
28 |
Correct |
19 ms |
76120 KB |
Output is correct |
29 |
Correct |
19 ms |
76120 KB |
Output is correct |
30 |
Correct |
19 ms |
76324 KB |
Output is correct |
31 |
Correct |
19 ms |
76120 KB |
Output is correct |
32 |
Correct |
19 ms |
76120 KB |
Output is correct |
33 |
Correct |
21 ms |
76120 KB |
Output is correct |
34 |
Correct |
19 ms |
76380 KB |
Output is correct |
35 |
Correct |
20 ms |
76380 KB |
Output is correct |
36 |
Correct |
20 ms |
76380 KB |
Output is correct |
37 |
Correct |
21 ms |
76888 KB |
Output is correct |
38 |
Correct |
19 ms |
76636 KB |
Output is correct |
39 |
Correct |
252 ms |
89428 KB |
Output is correct |
40 |
Correct |
245 ms |
89424 KB |
Output is correct |
41 |
Correct |
228 ms |
88652 KB |
Output is correct |
42 |
Correct |
228 ms |
87632 KB |
Output is correct |
43 |
Correct |
218 ms |
86416 KB |
Output is correct |
44 |
Correct |
121 ms |
86356 KB |
Output is correct |
45 |
Correct |
765 ms |
177232 KB |
Output is correct |
46 |
Correct |
263 ms |
131996 KB |
Output is correct |
47 |
Correct |
327 ms |
107680 KB |
Output is correct |
48 |
Correct |
775 ms |
115572 KB |
Output is correct |
49 |
Correct |
696 ms |
115384 KB |
Output is correct |
50 |
Correct |
357 ms |
107860 KB |
Output is correct |
51 |
Correct |
354 ms |
108072 KB |
Output is correct |
52 |
Correct |
386 ms |
102224 KB |
Output is correct |
53 |
Correct |
1534 ms |
222484 KB |
Output is correct |
54 |
Correct |
377 ms |
93412 KB |
Output is correct |
55 |
Correct |
35 ms |
77404 KB |
Output is correct |
56 |
Correct |
35 ms |
76888 KB |
Output is correct |
57 |
Correct |
190 ms |
86424 KB |
Output is correct |
58 |
Correct |
78 ms |
85448 KB |
Output is correct |
59 |
Runtime error |
221 ms |
262144 KB |
Execution killed with signal 9 |
60 |
Halted |
0 ms |
0 KB |
- |