| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 896097 | starchan | 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 "race.h"
#include<bits/stdc++.h>
using namespace std;
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)2e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
int n, k;
vector<in> adj[MX];
int sz[MX];
vector<int> curr;
vector<bool> cut;
stack<vector<in>> wow;
void dfs1(int u, int p)
{
sz[u] = 1;
for(in vw: adj[u])
{
int v = vw.f;
if(cut[v])
continue;
if(v == p)
continue;
dfs1(v, u);
sz[u]+=sz[v];
}
return;
}
vector<in> comp[MX];
vector<int> centr[MX];
int centroid(int root, int u, int p)
{
for(in vw: adj[u])
{
int v = vw.f;
if(cut[v])
continue;
if(v==p)
continue;
if(2*sz[v] > sz[root])
return centroid(root, v, u);
}
return u;
}
void dfs2(int u, int p, int lvl, int d)
{
curr.pb({d, lvl});
for(in vw: adj[u])
{
int v = vw.f;
int w = vw.s;
if(cut[v])
continue;
if(v==p)
continue;
int cost = d+w;
if(cost > k)
cost = k+1;
dfs2(root, v, u, lvl+1, cost);
}
return;
}
int centroid_decomposition(int u)
{
dfs1(u, -1);
int root = centroid(u, u, -1);
cut[root] = 1;
for(in vw: adj[root])
{
int v = vw.f;
if(cut[v])
continue;
curr.clear();
dfs2(v, -root, 1, vw.s);
wow.push(curr);
int w = centroid_decomposition(v);
comp[w] = wow.top();
wow.pop();
}
return root;
}
int dfs3(int u, int p)
{
int ans = n+1;
map<int, int> freq;
freq[0] = 0;
for(int v: centr[u])
{
ans = min(ans, dfs3(v, u));
for(in L_edge: comp[v])
{
int L = L_edge.f;
int dep = L_edge.s;
if(L > k)
continue;
if(freq.find(k-L) == freq.end())
continue;
ans = min(ans, dep+freq[k-L]);
}
for(in L_edge: comp[v])
{
int L = L_edge.f;
int dep = L_edge.s;
if(freq.find(L) == freq.end())
freq[L] = dep;
else
freq[L] = min(freq[L], dep);
}
}
return ans;
}
int best_path(int N, int K, int h[][2], int L[])
{
n = N;
k = K;
for(int i = 1; i <= n; i++)
{
adj[i].clear();
centr[i].clear();
}
for(int i = 0; i < n-1; i++)
{
int u = h[i][0];
int v = h[i][1];
u++;
v++;
int l = L[i];
adj[u].pb({v, l});
adj[v].pb({u, l});
}
cut.assign(n+1, 0);
int root = centroid_decomposition(1);
int ans = dfs3(root, -1);
if(ans == (n+1))
ans = -1;
return ans;
}
/*
signed main()
{
int V, KK;
cin >> V >> KK;
int h[V-1][2];
int L[V-1];
for(int i = 0; i < V-1; i++)
cin >> h[i][0] >> h[i][1] >> L[i];
int ok = best_path(V, KK, h, L);
cout << ok << endl;
return 0;
}
*/