| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 834486 | emad234 | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define ll long long
const ll mod = 1e9 + 7;
const ll mxN = 5e5 + 5;
#define MAX_N 500000
vector<vector<pair<ll,ll>>>v;
map<ll,ll>mp[mxN];
ll vis[mxN];
ll n, k;
ll sh[mxN],sha[mxN];
ll ans;
ll p[mxN];
void dfs(ll u){
vis[u] = 1;
for(auto ch : v[u]){
if(!vis[ch.F]){
dfs(ch.F);
ll a = u,b = ch.F;
if(mp[p[a]].size() < mp[p[b]].size()){
swap(a,b);
}
if(b == u){
// cout<<a<<'\n';
// for(auto x : mp[p[a]]) {
// cout<<x.first + sh[p[a]]<<' '<<x.second<<'\n';
// }
// cout<<b<<'\n';
// for(auto x : mp[p[b]]) {
// cout<<x.first + sh[p[b]]<<' '<<x.second<<'\n';
// }
for(auto x : mp[p[b]]) {
if(mp[p[a]][k - x.first - sh[p[b]] - sh[p[a]] - ch.S] + sha[p[a]])
ans = min(ans, x.second + sha[p[b]] + mp[p[a]][k - x.first - sh[p[b]] - sh[p[a]] - ch.S] + sha[p[a]] + 1);
}
for(auto x : mp[p[b]]){
if(mp[p[a]][x.first - ch.S + sh[p[b]] - sh[p[a]]])
mp[p[a]][x.first - ch.S + sh[p[b]] - sh[p[a]]] = min(mp[p[a]][x.first - ch.S + sh[p[b]] - sh[p[a]]],x.second - 1 + sha[p[b]]);
else mp[p[a]][x.first - ch.S + sh[p[b]] - sh[p[a]]] = x.second - 1 + sha[p[b]];
}
sh[p[a]] += ch.S;
sha[p[a]]++;
}else{
// cout<<a<<'\n';
// for(auto x : mp[p[a]]) {
// cout<<x.first + sh[p[a]]<<' '<<x.second + sha[p[a]]<<'\n';
// }
// cout<<b<<'\n';
// for(auto x : mp[p[b]]) {
// cout<<x.first + sh[p[b]]<<' '<<x.second + sha[p[b]]<<'\n';
// }
for(auto x : mp[p[b]]) {
if(mp[p[a]][k - x.first - sh[p[b]] - sh[p[a]] - ch.S] + sha[p[a]])
ans = min(ans, x.second + sha[p[b]] + mp[p[a]][k - x.first - sh[p[b]] - sh[p[a]] - ch.S] + sha[p[a]] + 1);
}
for(auto x : mp[p[b]]){
if(mp[p[a]][x.first + ch.S + sh[p[b]] - sh[p[a]]])
mp[p[a]][x.first + ch.S + sh[p[b]] - sh[p[a]]] = min(mp[p[a]][x.first + ch.S + sh[p[b]] - sh[p[a]]],x.second + 1 + sha[p[b]]);
else mp[p[a]][x.first + ch.S + sh[p[b]] - sh[p[a]]] = x.second + 1 + sha[p[b]];
}
}
p[b] = p[a];
}
}
mp[p[u]][-sh[p[u]]] = 0;
}
ll best_path(ll N, ll K, ll H[][2], ll L[])
{
n = N;k = K;
ans = 1e10;
memset(vis,0,sizeof vis);
for(ll i = 1;i <= n;i++){
p[i] = i;
sh[i] = 0;
mp[i].clear();
}
v.clear();
v.resize(n + 1);
for (ll i = 0;i < n - 1;i++){
v[H[i][0] + 1].push_back({H[i][1] + 1,L[i]});
v[H[i][1] + 1].push_back({H[i][0] + 1,L[i]});
}
dfs(1);
if(ans == 1e10) ans = -1;
return ans;
}
//
// static ll N, K;
// static ll H[MAX_N][2];
// static ll L[MAX_N];
// static ll solution;
// inline
// void my_assert(ll e) {if (!e) abort();}
// void read_input()
// {
// ll i;
// my_assert(2==scanf("%d %d",&N,&K));
// for(i=0; i<N-1; i++)
// my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
// }
//
// main()
// {
// read_input();
// best_path(N,K,H,L);
// cout<<ans;
// return 0;
// }