#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define rfr(i, n, m) for(int i = (n); i >= (m); i --)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int i_inf = 1e9+1;
const ll inf = 2e18;
const ll mod = 998244353;
const ld eps = 1e-13;
const ld pi = 3.14159265359;
const int mxn = 1e5+5;
mt19937 _rand(time(NULL));
#include "swap.h"
vector<pii> g[mxn];
int n, m;
int sparse[mxn][20];
int mis[mxn][20];
int mxw[mxn][20];
int depth[mxn];
int minc[mxn];
void dfs(int u, int p, int val, int val2){
sparse[u][0] = p;
fr(i, 1, 20) sparse[u][i] = sparse[sparse[u][i-1]][i-1];
mis[u][0] = val;
fr(i, 1, 20) mis[u][i] = min(mis[u][i-1], mis[sparse[u][i-1]][i-1]);
mxw[u][0] = val2;
fr(i, 1, 20) mxw[u][i] = max(mxw[u][i-1], mxw[sparse[u][i-1]][i-1]);
int mi1 = i_inf, c1 = -1;
int mi2 = i_inf;
for(auto e : g[u]){
if(e.st == p) continue;
if(e.nd < mi1){
mi2 = mi1;
mi1 = e.nd;
c1 = e.st;
}
else if(e.nd < mi2){
mi2 = e.nd;
}
}
minc[u] = mi1;
for(auto e : g[u]){
if(e.st == p) continue;
depth[e.st] = depth[u] + 1;
if(e.st != c1){
dfs(e.st, u, mi1, e.nd);
}
else{
dfs(e.st, u, mi2, e.nd);
}
}
}
int lca(int a, int b){
int mind = min(depth[a], depth[b]);
for(int i = 19; i >= 0; i --){
if(depth[a] - (1<<i) >= mind) a = sparse[a][i];
if(depth[b] - (1<<i) >= mind) b = sparse[b][i];
}
if(a == b) return a;
for(int i = 19; i >= 0; i --){
if(sparse[a][i] != sparse[b][i]){
a = sparse[a][i];
b = sparse[b][i];
}
}
return sparse[a][0];
}
int best_spot(int u, int p){
int ret = minc[u];
for(int i = 19; i >= 0; i --){
if(depth[u] - (1<<i) > depth[p]){
ret = min(ret, mis[u][i]);
u = sparse[u][i];
}
}
return ret;
}
int cost(int u, int p){
int ret = 0;
for(int i = 19; i >= 0; i --){
if(depth[u] - (1<<i) >= depth[p]){
ret = max(ret, mxw[u][i]);
u = sparse[u][i];
}
}
return ret;
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W){
n = N, m = M;
fr(i, 0, m){
g[U[i]].pb({V[i], W[i]});
g[V[i]].pb({U[i], W[i]});
}
fr(i, 0, n){
sort(all(g[i]), [](const pii A, const pii B){
return A.nd < B.nd;
});
}
dfs(0, 0, i_inf, i_inf);
}
int getMinimumFuelCapacity(int X, int Y) {
int k = lca(X, Y);
int bs1 = best_spot(X, k);
int bs2 = best_spot(Y, k);
int spot = min(bs1, bs2);
for(auto u : g[k]){
if(u.st == X || u.st == Y) continue;
spot = min(spot, u.nd);
break;
}
int c1 = cost(X, k);
int c2 = cost(Y, k);
int tc = max(spot, max(c1, c2));
if(tc == i_inf) tc = -1;
return tc;
}/*
int main(){
cin >> n >> m;
vector<int> U(m);
vector<int> V(m);
vector<int> W(m);
fr(i, 0, m){
cin >> U[i] >> V[i] >> W[i];
}
init(n, m, U, V, W);
int i, j;
while(cin >> i >> j){
cout<<getMinimumFuelCapacity(i, j)<<endl;
}
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1861 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1861 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1861 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
