#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#include <vector>
#define all(x) x.begin() , x.end()
const int N = 2e5;
int n , m;
vector<int> u , v , w;
void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) {
n = N , m = M , u = U , v = V , w = W;
}
bool vis[N] ;
int edges = 0;
int nodes = 0;
bool f = 0;
void dfs(int x , vector<vector<int>> &adj){
if (vis[x]) return ;
vis[x] = 1;
nodes++;
if (adj[x].size() > 2) f = 1;
for (auto i : adj[x]){
edges++;
dfs(i , adj);
}
}
bool check(int x , int y , int md){
vector<vector<int>> adj(n);
for (int i =0 ; i < n; i++) vis[i] = 0;
nodes = 0; edges = 0; f = 0;
for (int i = 0 ; i < m ; i++){
if (w[i] > md) continue;
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs(x , adj);
if (!vis[y]) return 0;
edges/=2;
//cout << nodes << ' ' << edges << ' ' << md << ' ';
//cout << f << '\n';
if (edges > nodes - 1) return 1;
return f;
}
int getMinimumFuelCapacity(int X, int Y) {
int l = 0 ,r = 1e9 , md;
while(l<=r){
md = (l+r)>>1;
if (check(X , Y , md)) r = md-1;
else l = md+1;
}
return (r+1 > 1e9 ? -1 : r+1);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |