This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int n, m;
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;
for (int i=0; i<m; i++)
{
edge.push_back({v[i], u[i], w[i]});
}
}
int getMinimumFuelCapacity(int x, int y) {
sort(edge.begin(), edge.end(), cmp);
link.resize(n, 0);
volume.resize(n, 0);
swapable.resize(n, 0);
degree.resize(n, 0);
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);
if (same(x, y) && swapable[find(x)]) {return w;}
}
return -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... |