#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=2e5+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].pb({0,0});
for(auto y : g[v]){
ll i=y.fr;
ll 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(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);
return ans;
}
/*
4 3
0 1 1
1 2 2
1 3 4
2
*/
Compilation message
race.cpp: In function 'void calc(int, int)':
race.cpp:69: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]
69 | for(ll j=0;j<dp[i].size();j++){
| ~^~~~~~~~~~~~~
race.cpp:75: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]
75 | if(low<dp[v].size() && dp[v][low].fr==k-j.fr)chmin(ans,dp[v][low].sc+j.sc);
| ~~~^~~~~~~~~~~~~
race.cpp:77: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]
77 | while(l<dp[i].size() || r<dp[v].size()){
| ~^~~~~~~~~~~~~
race.cpp:77: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]
77 | while(l<dp[i].size() || r<dp[v].size()){
| ~^~~~~~~~~~~~~
race.cpp:78: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]
78 | if(l<dp[i].size() && r<dp[v].size()){
| ~^~~~~~~~~~~~~
race.cpp:78: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]
78 | if(l<dp[i].size() && r<dp[v].size()){
| ~^~~~~~~~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:115:10: warning: unused variable 'j' [-Wunused-variable]
115 | ll i,j,a,b;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
23 ms |
37348 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
23 ms |
37348 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
23 ms |
37348 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
23 ms |
37348 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |