#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
struct edge{
int u, v, w;
};
bool comp(edge x, edge y){
return x.w < y.w;
}
int n, m;
const int maxn = 1e5 + 69;
vector <pair<int, int>> adj[maxn], g[maxn];
int root[maxn], mn[maxn], r2[maxn];
set <pair<int, pair<int, int>>> path, ans;
edge e[2 * maxn];
int mp[maxn];
multiset <int> ok;
int l2;
void dfs2(int u, int need, int par){
if (u == need){
l2 = *(--ok.end());
}
for (auto [v, w] : adj[u]){
if (v == par) continue;
ok.insert(w);
dfs2(v, need, u);
ok.erase(ok.find(w));
}
}
int find2(int x){
if (x == r2[x]) return x;
return r2[x] = find2(r2[x]);
}
bool unite2(int x, int y){
x = find2(x); y = find2(y);
if (x == y) return false;
r2[y] = x;
return true;
}
int find(int x) {
if (x == root[x]) return x;
return root[x] = find(root[x]);
}
bool unite(int x, int y){
x = find(x); y = find(y);
if (x == y) return false;
root[y] = x;
return true;
}
pair<int, pair<int, int>> get(int u, int v, int w){
return {w, {u, v}};
}
void dfs(int u, int need, int par){
if (need == u) ans = path;
for (auto [v, w] : adj[u]){
if (v == par) continue;
path.insert(get(u, v, w));
path.insert(get(v, u, w));
dfs(v, need, u);
path.erase(get(u, v, w));
path.erase(get(v, u, w));
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N;
m = M;
vector <pair<int, pair<int, int>>> vec;
for (int i = 0; i < m; i++){
vec.push_back({W[i], {U[i], V[i]}});
}
sort(vec.begin(), vec.end());
for (int i = 0; i < m; i++){
e[i].u = vec[i].second.first;
e[i].v = vec[i].second.second;
e[i].w = vec[i].first;
}
for (int i = 0; i < n; i++){
root[i] = r2[i] = i;
mn[i] = 1e9 + 1;
}
for (int i = 0; i < m; i++){
auto x = e[i];
// cout << x.u << " " << x.v << "BRUH\n";
if (unite(x.u, x.v)){
adj[x.u].push_back({x.v, x.w});
adj[x.v].push_back({x.u, x.w});
// cout << "ADDED " << x.u << " " << x.v << " " << x.w << "\n";
} else {
mn[x.u] = min(mn[x.u], x.w);
mn[x.v] = min(mn[x.v], x.w);
if (unite(x.u, x.v)){
g[x.u].push_back({x.v, x.w});
g[x.v].push_back({x.u, x.w});
}
}
}
}
int getMinimumFuelCapacity(int x, int y) {
dfs(x, y, -1);
l2 = 1e9 + 1;
dfs2(x, y, -1);
for (int i = 0; i < n; i++) mp[i] = 0;
int lol = 0;
for (auto x : ans) {
lol = max(lol, x.first);
mp[x.second.first]++;
mp[x.second.second]++;
}
int l1 = l2;
// cout << ans.size() << "\n";
// for (auto x : ans) {
// cout << x.first << " " << x.second.first << " " << x.second.second << "\n";
// }
for (int i = 0; i < m; i++){
if (ans.find(get(e[i].u, e[i].v, e[i].w)) == ans.end()){
if (mp[e[i].u] && mp[e[i].v]) l1 = min(l1, e[i].w);
else if (e[i].u == x || e[i].u == y || e[i].v == x || e[i].v == y);
else if (mp[e[i].u] || mp[e[i].v]) l1 = min(l1, e[i].w);
}
}
if (l1 > 1e9) return -1;
else return max(l1, lol);
}
// int main(){
// int n, m; cin >> n >> m;
// vector <int> u(m), v(m), w(m);
// for (auto &x : u) cin >> x;
// for (auto &x : v) cin >> x;
// for (auto &x : w) cin >> x;
// init(n, m, u, v, w);
// int q; cin >> q;
// while (q--){
// int x, y; cin >> x >> y;
// cout << getMinimumFuelCapacity(x, y) << "\n";
// }
// return 0;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
