| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1052125 | JosephA | 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 pb push_back
#define SZ(x) (int)(x).size()
typedef long long ll;
struct E { int v; ll w; };
struct Tree{
int n, l;
vector<vector<int>>adj;
vector<ll>depth, parent, subtree, tin, tout;
vector<vector<int>>up;
int timer;
Tree(int n){
this->n = n;
adj.resize(n + 1);
depth.resize(n + 1);
parent.resize(n + 1);
subtree.resize(n + 1);
tin.resize(n + 1);
tout.resize(n + 1);
timer = 0;
l = ceil(log2(n));
up.resize(n + 1, vector<int>(l + 1));
}
void addEdge(int u, int v){
adj[u].pb(v);
adj[v].pb(u);
}
void init(){
dfs(1, -1); dfs1(1, -1);
}
void dfs(int u, int p){
tin[u] = ++timer;
up[u][0] = (p == -1 ? 1 : p);
for(int i = 1; i <= l; i++){
up[u][i] = up[up[u][i - 1]][i - 1];
}
for(auto v : adj[u]){
if(v != p){
depth[v] = depth[u] + 1;
dfs(v, u);
}
}
tout[u] = ++timer;
} // O(nlogn)
bool is_ancestor(int u, int v){
return tin[u] <= tin[v] && tout[u] >= tout[v];
} // O(1)
int lca(int u, int v){
if(is_ancestor(u, v)) return u;
if(is_ancestor(v, u)) return v;
for(int i = l; i >= 0; i--){
if(!is_ancestor(up[u][i], v)){
u = up[u][i];
}
}
return up[u][0];
} // O(logn)
int dist(int u, int v){
return depth[u] + depth[v] - 2 * depth[lca(u, v)];
} // O(logn)
int get_kth_ancestor(int u, int k){
for(int i = l; i >= 0; i--){
if(k & (1 << i)){
u = up[u][i];
}
}
return u;
} // O(logn)
void dfs1(int u, int p){
subtree[u] = 1;
for(auto v : adj[u]){
if(v != p){
dfs1(v, u);
subtree[u] += subtree[v];
}
}
} // O(n)
bool is_leaf(int u){
return u!=1 && SZ(adj[u]) == 1;
} // O(1)
};
int best_path(int n, int k, int edges_[][2], int weights[]) {
vector<tuple<int, int, ll>> edges;
Tree t(n + 1);
for(int i = 1; i < n; i++) {
edges.pb({edges[i][0], edges_[i][1], 0LL});
t.addEdge(edges[i][0], edges[i][1]);
}
t.init();
for(int i = 0; i < n-1; i++) {
get<2>(edges[i]) = weights[i];
}
vector<E> adj[n + 1]; for(int i = 0; i < SZ(edges); i++) {
int u, v; ll w; tie(u, v, w) = edges[i];
adj[u].pb({v, w}); adj[v].pb({u, w});
}
vector<ll> dist(n + 1, 0LL), dp(n + 1, 0LL);
function<void(int, int)> init = [&](int u, int p) {
for(auto [v, w] : adj[u]) if(v != p) {
dp[v] = dp[u] + w; init(v, u);
}
}; init(0, 0);
auto distance = [&](int u, int v) { return t.dist(u, v); };
int ans = 1e9;
map<ll, int> s[n + 1];
auto MERGE = [&](int u, int v) {
if(s[v].find(k + dp[u]) != s[v].end()) ans = min(ans, distance(u, s[v][k + dp[u]]));
if(s[u].size() < s[v].size()) swap(s[u], s[v]);
for(auto [d, l] : s[v]) {
if(s[u].find(-d + 2*dp[u] + k) != s[u].end())
ans = min(ans, distance(l, s[u][-d + 2*dp[u] + k]));
if(!s[u].count(d)) s[u][d] = l;
else s[u][d] = (t.depth[l] < t.depth[s[u][d]] ? l : s[u][d]);
}
};
function<void(int, int)> dfs = [&](int u, int p) {
for(auto [v, w] : adj[u]) if(v != p) {
dfs(v, u); MERGE(u, v);
}
s[u][dp[u]] = u;
};
dfs(0, -1);
return (ans == 1e9 ? -1 : ans);
}