| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 804950 | Gangsta | 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.
// a >> b = a / pow(2,b)
// a << b = a * pow(2,b)
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define sz size()
#define ss second
#define ff first
#define N 200001
#define LOG 20
#define pii pair<int,long long int>
using namespace std;
int n, m, u[N], v[N], w[N], par[N], lvl[N], P[N][LOG];
ll p[N][LOG];
vector<pii> adj[N];
void dfs(int nd, int pr){
for(auto i : adj[nd]){
if(i.ff == pr) continue;
P[i.ff][0] = nd;
p[i.ff][0] = i.ss;
lvl[i.ff] = lvl[nd] + 1;
dfs(i.ff,nd);
}
}
pii olala(int nd, int k){
ll sum = 0;
for(int i = LOG - 1; i >= 0; i--){
if(k >> i&1){
sum += p[nd][i];
nd = P[nd][i];
}
}
return {nd,sum};
}
int LCA(int a, int b){
if(lvl[a] < lvl[b]) b = olala(b,lvl[b] - lvl[a]).ff;
else if(lvl[a] > lvl[b]) a = olala(a,lvl[a] - lvl[b]).ff;
if(a == b) return a;
for(int i = LOG - 1; i >= 0; i--){
if(P[a][i] != P[b][i]){
a = P[a][i];
b = P[b][i];
}
}
return P[a][0];
}
int best_path(int n, int k, int h[N][2], ll l[N]){
int mn = N;
for(int i = 1; i < n; i++){
adj[h[i][0]].pb({h[i][1],l[i]});
adj[h[i][1]].pb({h[i][0],l[i]});
}
dfs(0,-1);
for(int i = 1; i < LOG; i++){
for(int j = 1; j <= n; j++){
if(P[j][i-1]){
P[j][i] = P[P[j][i-1]][i-1];
p[j][i] = p[j][i-1] + p[P[j][i-1]][i-1];
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
int c = LCA(i,j);
ll jogap = olala(i,lvl[i] - lvl[c]).ss + olala(j,lvl[j] - lvl[c]).ss;
if(jogap == k) mn = min(mn,lvl[i] + lvl[j] - 2*lvl[c]);
}
}
if(mn == N) return -1;
else return mn;
}
//int main(){
// int n, k, h[N][2];
// ll l[N];
// cin >> n >> k;
// for(int i = 1; i < n; i++){
// cin >> h[i][0] >> h[i][1];
// }
// for(int i = 1; i < n; i++){
// cin >> l[i];
// }
// cout << best_path(n,k,h,l);
//}