#include<bits/stdc++.h>
#include "swap.h"
using namespace std;
const int N = 2e5 + 5;
int n , m;
vector<pair<int, int>> adj[N];
int P[N][20] , mn[N][22] , depth[N] , dp[N][22];
void dfs(int u , int p = -1){
P[u][0] = p;
for(int i = 1;i <= 17; ++i) P[u][i] = P[P[u][i- 1]][i -1] , mn[u][i] = min(mn[u][i - 1] , mn[P[u][i - 1]][i - 1]);
for(auto x : adj[u]){
int v = x.first , w= x.second;
if(v == p)continue;
mn[v][0] = w;
depth[v] = depth[u] + 1;
dfs(v , u);
}
}
void Q(int u, int p = -1){
for(auto x : adj[u]){
int v= x.first , w = x.second;
if(v==p)continue;
Q(v , u);
}
if(p==-1)return;
for(auto x : adj[p]) if(x.first != u)dp[u][0] = min(dp[u][0] , x.second);
for(int i =1; i <= 20; ++i) dp[u][i] = min(dp[u][i - 1] , dp[P[u][i - 1]][i - 1]);
}
int MN = 2e9 , Y = 2e9;
void LCA(int u , int v){
if(depth[u] < depth[v])swap(u , v);
int k = depth[u] - depth[v];
for(int i = 17; ~i; --i){
if(k>>i & 1)MN = min(MN , mn[u][i]) , Y = min(Y , dp[u][i]) ,u= P[u][i];
}
return;
for(int i = 17; ~i; --i){
if(P[u][i] != P[v][i]){
MN = min({MN , mn[u][i] , mn[v][i]});
Y = min({Y , dp[u][i] , dp[v][i]});
u =P[u][i] , v= P[v][i];
}
}
Y = min({Y , dp[u][0] , dp[v][0]});
MN = min({MN ,mn[u][0] , mn[v][0]});
}
void init(int N, int M,vector<int> U, vector<int> V, vector<int> W){
n = N, m = M;
for(int i = 1; i <= m; ++i){
adj[U[i-1]].emplace_back(V[i - 1] , W[i - 1]);
adj[V[i -1]].emplace_back(U[i - 1] ,W[i - 1]);
}
for(int i= 1; i<= n; ++i)for(int j =0; j <= 20; ++j) dp[i][j] = mn[i][j] = 2e9;
dfs(1);
Q(1);
}
int getMinimumFuelCapacity(int u, int v) {
LCA(u , v);
if(Y == 2e9)return -1;
else return max(Y , MN);
}
/*
int main (){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
int u , v , w;
for(int i = 1; i <= m; ++i){
cin >> u >> v >> w;
adj[u].emplace_back(v , w);
adj[v].emplace_back(u ,w);
}
for(int i= 1; i<= n; ++i)for(int j =0; j <= 20; ++j) dp[i][j] = mn[i][j] = 2e9;
dfs(1);
Q(1);
}
*/
Compilation message
swap.cpp: In function 'void Q(int, int)':
swap.cpp:22:26: warning: unused variable 'w' [-Wunused-variable]
22 | int v= x.first , w = x.second;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
