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 "swap.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
struct dsu{
int n;
vector<int> sz, p;
vector<bool> ok;
vector<int> adj;
dsu(int nn){
n = nn;
sz.resize(n, 1);
p.resize(n);
ok.resize(n, 0);
adj.resize(n, 0);
for(int i = 0; i < n; i++) p[i] = i;
}
int get(int x){
if(p[x] != x) p[x] = get(p[x]);
return p[x];
}
void unite(int a, int b){
adj[a]++, adj[b]++;
if(adj[a] >= 3) ok[get(a)] = 1;
if(adj[b] >= 3) ok[get(b)] = 1;
a = get(a), b = get(b);
if(a == b){
ok[a] = 1;
return;
}
if(sz[b] > sz[a]) swap(a, b);
sz[a]+=sz[b];
sz[b] = 0;
ok[a] = ok[a]|ok[b];
ok[b] = 0;
p[b] = a;
}
};
int n, m;
vector<tuple<int, int, int>> edges;
void init(int n, int m, vector<int> u, vector<int>v, vector<int>w){
::n = n, ::m = m;
for(int i = 0; i < m; i++){
edges.pb({w[i], u[i], v[i]});
}
sort(edges.begin(), edges.end());
}
int getMinimumFuelCapacity(int X, int Y){
dsu ds(n);
for(int i = 0; i < m; i++){
auto [w, a, b] = edges[i];
ds.unite(a, b);
if(ds.get(X) == ds.get(Y) && ds.ok[ds.get(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... |