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) {
if (x == link[x]) return x;
return link[x] = find(link[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);
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]});
}
sort(edge.begin(), edge.end(), cmp);
link.resize(n, 0);
volume.resize(n, 0);
swapable.resize(n, 0);
degree.resize(n, 0);
}
int getMinimumFuelCapacity(int x, int y) {
for (int i=0; i<n; i++)
{
link[i]=i;
volume[i]=1;
swapable[i]=0;
degree[i]=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);
degree[u]++; degree[v]++;
if (same(u, v) || degree[u] >= 3 || degree[v] >= 3)
{
swapable[find(u)] = true;
swapable[find(v)] = 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... |