| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1145251 | asdfghjk | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define con continue
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<ll,ll> pii;
const ll N = 1e5 + 5;
const ll MOD = 1e9 + 7;
const ll maxn = 6e5 + 5;
const ll inf = 1e9;
const ll INF = 1e18;
const ll K = 31;
/*vector <ll> z_function(string s){
// ll n = s.size();
// ll l = 0,r = 0;
// vector <ll> z(n);
// for(ll i = 1;i < n;i++){
// if(i <= r){
// z[i] = (r - i + 1,z[i - l]);
// }
// while(i + z[i] < n && s[z[i]] == s[z[i] + i]){
// z[i]++;
// }
// if(i + z[i] - 1 > r){
// r = i + z[i]-1;
// l = i;
// }
// }
}*/
/*vector <ll> prefix_function(string s){
ll n = s.size();
vector <ll> pi(n,0);
for(ll i = 1;i < n;i++){
ll j = pi[i - 1];
while(j > 0 && s[i] != s[j]){
j = pi[j - 1];
}
if(s[i] == s[j])++j;
pi[i] = j;
}
return pi;
}*/
int n,ans = -1;
ll sz[N],was[N];
vector <pair<ll,ll> > g[N];
void cal(ll v,ll p){
sz[v] = 1;
for(auto [to,w] : g[v]){
if(was[to] || to == p)con;
cal(to,v);
sz[v] += sz[to];
}
}
ll get_centr(ll v,ll p,ll len){
for(auto [to,w] : g[v]){
if(was[to] || to == p)con;
if((sz[to] *2 > len)){
return get_centr(to,v,len);
}
}
return v;
}
ll k;
map<ll,ll> val;
ll dep[N],dis[N];
void dfs(ll v,ll p){
if(dis[v] == k){
if(ans != -1)ans= min(ans,dep[v]);
else ans = dep[v];
}
else if(dis[v] < k){
if(val[(k - dis[v])] != 0){
if(ans != -1)ans = min(ans,dep[v] + val[(k - dis[v])]);
else ans = dep[v] + val[(k - dis[v])];
}
}
for(auto [to,w] : g[v]){
if(was[to] || to == p)con;
dep[to] = dep[v] + 1;
dis[to] = dis[v] + w;
dfs(to,v);
}
}
void add(ll v,ll p){
if(val[dis[v]] == 0){
val[dis[v]] = dep[v];
}
else if(dis[v] < k){
val[dis[v]] = min(val[dis[v]],dep[v]);
}
for(auto [to,w] : g[v]){
if(was[to] || to == p)con;
dep[to] = dep[v] + 1;
dis[to] = dis[v] + w;
add(to,v);
}
}
void centr_decop(ll v){
cal(v,0);
ll c = get_centr(v,v,sz[v]);
dep[c] = 0;
dis[c] = 0;
val.clear();
for(auto [to,w] : g[v]){
if(was[to])con;
dep[to] = 1;
dis[to] = w;
dfs(to,c);
add(to,c);
}
was[c] = 1;
for(auto [to,w] : g[v]){
if(was[to])con;
centr_decop(to);
}
}
int best_path(int nn,int k2,int h[][2],int l[]){
n = nn;
k = k2;
for(int i = 1;i < n;i++){
int u= h[i][0];
int v = h[i][1];
int w = l[i];
g[u].pb({v,w});
g[v].pb({u,w});
}
centr_decop(1);
return ans;
}
//void solve(){
// ll n =
//}
//main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// ll abd = 1;
//// freopen("yinyang.in","r",stdin);
//// freopen("yinyang.out","w",stdout);
//
//// cin >> abd;
// for(ll i = 1;i <= abd;i++){
// solve();
// }
//}