| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 804954 |
2023-08-03T12:08:13 Z |
Gangsta |
Race (IOI11_race) |
C++14 |
|
4 ms |
4948 KB |
// 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,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], int 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);
//}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
