| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 463800 | ezdp | 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.
#pragma GCC target ("sse4")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define endl '\n'
#define pb push_back
#define fr first
#define sc second
#define ll long long int
#define ld long double
#define bit(idx) idx&(-idx)
#define bin(x) bitset<32>(x).to_string()
#define all(A) A.begin(), A.end()
#define de(x) cout << #x << " = " << x << endl;
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using matrix = vector<vector<T>>;
/// find_by_order(x) -> x-th element in the set
/// order_of_key(x) -> how many elements are smaller than x
/// insert(x) -> inserts x into the set
const ll MAXN = 2e5 + 5;
const ll MAXL = 18;
const ll INF = 1e16 + 16;
ll n, k, up[MAXN][MAXL], len[MAXN], depth[MAXN], tin[MAXN], tout[MAXN], T, ans = INF, root = 1, used[MAXN], sz[MAXN], mn[MAXN];
matrix<pair<ll, ll>> G;
matrix<ll> C;
vector<pair<ll, ll>> upd;
set<ll> rem;
void dfs_lca(ll u = 1, ll p = 1, ll d = 0, ll L = 0){
tin[u] = ++ T;
depth[u] = d;
len[u] = L;
up[u][0] = p; for(int i = 1; i < MAXL; i ++) up[u][i] = up[up[u][i - 1]][i - 1];
for(auto [v, l] : G[u]){
if(v != p){
dfs_lca(v, u, d + 1, L + l);
}
}
tout[u] = ++ T;
}
bool is_ancestor(ll u, ll v){
return (tin[u] <= tin[v] && tout[v] <= tout[u]);
}
ll lca(ll u, ll v){
if(is_ancestor(u, v))
return u;
if(is_ancestor(v, u))
return v;
for(int i = MAXL - 1; i >= 0; i --){
if(!is_ancestor(up[u][i], v)){
u = up[u][i];
}
}
return up[u][0];
}
pair<ll, ll> dist(ll u, ll v){
ll lc = lca(u, v);
return {depth[u] + depth[v] - 2 * depth[lc], len[u] + len[v] - 2 * len[lc]};
}
ll find_size(ll u, ll p = -1){
if(used[u]) return 0;
sz[u] = 1;
for(auto [v, l] : G[u]){
if(v != p && !used[v]){
sz[u] += find_size(v, u);
}
}
return sz[u];
}
ll find_centroid(ll u, ll p, ll cn){
for(auto [v, l] : G[u]){
if(v != p && !used[v] && sz[v] > cn / 2){
return find_centroid(v, u, cn);
}
}
return u;
}
void init_centroid(ll u = 1, ll p = -1){
find_size(u);
ll c = find_centroid(u, -1, sz[u]);
used[c] = true;
if(p == -1){ root = c; }
else{ C[c].pb(p); C[p].pb(c); }
for(auto [v, l] : G[c]){
if(!used[v]){
init_centroid(v, c);
}
}
}
void dfs2(ll u, ll p, ll c){
auto tmp = dist(u, c);
if(tmp.sc <= k){
ans = min(ans, mn[k - tmp.sc] + tmp.fr);
upd.pb({tmp.sc, tmp.fr});
rem.insert(tmp.sc);
}
for(auto v : C[u]){
if(v != p){
dfs2(v, u, c);
}
}
}
void dfs1(ll u, ll p){
mn[0] = 0;
for(auto v : C[u]){
dfs2(v, u, u);
for(auto [x, v] : upd) mn[x] = min(mn[x], v);
}
for(auto x : rem) mn[x] = INF;
for(auto v : C[u]){
if(v != p){
dfs1(v, u);
}
}
}
ll best_path(ll N, ll K, ll h[][2], ll L[]){
n = N; k = K;
for(int i = 0; i < n - 1; i ++){ G[h[i][0]].pb({h[i][1], L[i]}); G[h[i][1]].pb({h[i][0], L[i]}); }
for(int i = 0; i < MAXN; i ++) mn[i] = INF;
C.resize(n + 1);
G.resize(n + 1);
dfs_lca();
init_centroid();
dfs1(root, root);
return (ans == INF ? -1 : ans);
}
/**int main(){
cin >> n >> k;
for(int i = 0; i < n - 1; i ++){
int u, v, l; cin >> u >> v >> l;
G[u].pb({v, l});
G[v].pb({u, l});
}
cout << (ans == INF ? -1 : ans) << endl;
}
/**
11 12
1 2 3
1 3 4
3 4 5
4 5 4
5 6 6
1 7 3
7 8 2
7 9 5
9 10 6
9 11 7
*/