#include <swap.h>
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<pair<int, int>>> adj;
vector<tuple<int, int, int>> edge;
vector<int> link;
vector<int> volume;
vector<bool> swapable;
vector<int> degree;
int find(int x) {
while (x != link[x]) x = link[x];
return x;
}
bool same(int a, int b) {
return find(a) == find(b);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (volume[a] < volume[b]) swap(a,b);
degree[a]++; degree[b]++;
if (degree[a] >= 3) swapable[a] = true;
if (degree[b] >= 3) swapable[b] = true;
volume[a] += volume[b];
swapable[a] = swapable[a] || swapable[b];
link[b] = a;
}
bool cmp(tuple<int, int, int> tul1, tuple<int, int, int> tul2)
{
return (get<2>(tul1) < get<2>(tul2));
}
void init(int n1, int m1, vector<int> v, vector<int> u, vector<int> w) {
n = n1;
m = m1;
adj.resize(n);
for (int i=0; i<m; i++)
{
adj[v[i]].push_back({u[i], w[i]});
adj[u[i]].push_back({v[i], w[i]});
edge.push_back({v[i], u[i], w[i]});
//edge.push_back({u[i], v[i], w[i]});
}
}
int getMinimumFuelCapacity(int x, int y) {
sort(edge.begin(), edge.end(), cmp);
link.resize(n);
volume.resize(n);
swapable.resize(n);
degree.resize(n);
for (int i=0; i<n; i++) {
link[i] = i;
volume[i] = 1;
}
for (auto e: edge)
{
int u = get<0>(e);
int v = get<1>(e);
int w = get<2>(e);
if (same(u, v)) {swapable[find(u)] = true;}
unite(u, v);
//cout<<u<<" "<<v<<" "<<"\n";
//cout<<degree[u]<<" "<<degree[v]<<" "<<swapable[y]<<"\n\n";
if (same(x, y) && swapable[find(x)]) {return w;}
}
}
Compilation message
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:74:1: warning: control reaches end of non-void function [-Wreturn-type]
74 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |