| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 480621 | CyberSleeper | Race (IOI11_race) | C++14 | 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>
#include "race.h"
#define pii pair<ll, ll>
#define fi first
#define se second
#define pb push_back
using namespace std;
const ll MX=200007, INF=1e9+7;
vector<pii> adj[MX];
map<ll, pii> ada[MX];
ll N, K, ret=INF;
void add(ll i, ll j, ll x){
if(ada[i].count(j)){
pii now=ada[i][j];
if(now.se>x)
now.se=x;
if(now.fi>now.se)
swap(now.fi, now.se);
ada[i][j]=now;
}else{
ada[i][j]={x, INF};
}
}
void calc(ll x){
cout << endl;
cout << x << endl;
for(auto ii:ada[x]){
ll i=ii.fi, j=K-i;
cout << "i: " << i << endl;
if(i>=(K+1)/2)
break;
if(ada[x].count(i) && ada[x].count(j)){
cout << i << ' ' << j << " good\n";
ret=min(ret, ada[x][i].fi+ada[x][j].fi);
cout << ada[x][i].fi << " ::: " << ada[x][j].fi << endl;
}
}
if(K%2==0){
ll k=K/2;
if(ada[x].count(k)){
pii tmp=ada[x][k];
if(tmp.se && tmp.se!=INF){
ret=min(ret, tmp.fi+tmp.se);
cout << "double: " << tmp.fi << ' ' << tmp.se << endl;
}
}
}
}
void DFS(ll par, ll wpar, ll x){
ada[x][0]={0, INF};
for(auto i:adj[x]){
ll v=i.fi, w=i.se;
if(v==par)
continue;
DFS(x, w, v);
if(ada[x].size()<ada[v].size())
swap(ada[x], ada[v]);
for(auto j:ada[v]){
ll tot=j.fi, sisa=K-tot;
pii cnt=j.se;
if(tot>K)
continue;
if(ada[x].count(sisa)){
ret=min(ret, ada[x][sisa].fi+ada[v][tot].fi);
}
add(x, tot, cnt.fi);
add(x, tot, cnt.se);
}
}
if(!x)
return;
vector<ll> delay;
for(auto i=ada[x].rbegin(); i!=ada[x].rend(); i++){
pair<ll, pii> tmp=*i;
tmp.se.fi++;
tmp.se.se++;
ada[x][tmp.fi+wpar]=tmp.se;
delay.pb(tmp.fi);
}
for(auto i:delay)
ada[x].erase(i);
}
ll best_path(ll n, ll k, ll H[][2], ll L[]){
N=n, K=k;
for(ll i=0, u, v, w; i<N-1; i++){
u=H[i][0], v=H[i][1], w=L[i];
adj[u].pb({v, w});
adj[v].pb({u, w});
}
DFS(0, 0, 0);
return (ret>=INF?-1:ret);
}