| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 287597 | crossing0ver | 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>
//#define int long long
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#include "race.h"
using namespace std;
const int MXN = 1e5+5;
vector<pii> adj[MXN];
int n,k,sz[MXN];
bool vis[MXN],bad[MXN];
int calcsize(int v,int p) {
sz[v] = 1;
for (auto i : adj[v]) {
int to = i.fi;
if (!bad[to] && to != p) {
calcsize(to,v);
sz[v] += sz[to];
}
}
return sz[v];
}
pii MN;
int SZ;
void getcenter(int v,int p) {
int mxsz = 0,sum = 0;
for (auto i : adj[v]) {
int to = i.fi;
if (to == p || bad[to]) continue;
getcenter(to,v);
mxsz = max(mxsz,sz[to]);
sum += sz[to];
}
int adit = SZ - sum - 1;
mxsz = max(mxsz,adit);
MN = min(MN,make_pair(mxsz,v));
}
const int MAXK = 1e6+6;
int dis[MAXK + 5];
int ans = INT_MAX;
void get(int v,int p,int depth,int val) {
if (val > k) return;
if (dis[k-val] && dis[k - val] + depth - 1 < ans)
ans = dis[k-val] + depth - 1;
for (auto i : adj[v]) {
int to = i.fi;
if (p != to && !bad[to])
get(to,v,depth+1,val + i.se);
}
}
void upd(int v,int p,int depth,int val,bool flag) {
if (dis[val] == 0 || dis[val] > depth)
dis[val] = depth;
if (flag == 0) dis[val] = 0;
for (auto i : adj[v]) {
int to = i.fi;
if (p!= to && !bad[to])
upd(to,v,depth+1,val + i.se,flag);
}
}
void dfs(int v,int p,int depth,bool keep) {
int big = -1,mxsz =- 1,money = -1;
for (auto i : adj[v]) {
int to = i.fi;
if (to != p && mxsz < sz[to]) {
// mxsz = sz[to];
/// big = to;
// money = i.se;
}
}
/* if (big + 1) {
get(big,v,depth+1,money);
upd(big,v,depth+1,money,1);
}*/
for (auto i : adj[v]) {
if (bad[to]) continu;
int to = i.fi;
//if (i == p || i == big)
/// continue;
get(to,v,2,i.se);
upd(to,v,2,i.se,1);
}
for (auto i : adj[v]) {
int to = i.fi;
if (to != p && !bad[to])
upd(to,v,depth+1,i.se,0);
}
}
void split(int v){
bool ok = 0;
for (auto i : adj[v])
if (!bad[i.fi]) ok = 1;
if (ok == 0) return;
SZ = calcsize(v,-1);
MN = {INT_MAX,0};
getcenter(v,-1);
int center = MN.se;
calcsize(center,-1);
dis[0] = 1;
dfs(center,-1,1,0);
bad[center] = 1;
for (auto & i : adj[center])
if (bad[i.fi] == 0)
split(i.fi);
}
int best_path(int n1, int k1, int H[][2], int L[])
{
n = n1;
k = k1;
for (int i = 0; i< n ;i++) {
adj[H[i][0]].pb({H[i][1],L[i]});
adj[H[i][1]].pb({H[i][0],L[i]});
}
split(0);
if (ans == INT_MAX) return -1;
return ans-1;
}