#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
class DisjointSet {
public:
int n, t = -1;
vector<vector<pair<int, int>>> p; // (time, data)
vector<vector<pair<int, int>>> sz;
vector<vector<pair<int, int>>> deg;
vector<vector<pair<int, int>>> cycle;
DisjointSet() {}
DisjointSet(int n) : n(n), p(n), sz(n), deg(n), cycle(n) {
for (int i = 0; i < n; i++) {
p[i].emplace_back(-1, i);
sz[i].emplace_back(-1, 1);
deg[i].emplace_back(-1, 0);
cycle[i].emplace_back(-1, 0);
}
}
int Find(int x) {
return p[x].back().second == x ? x : Find(p[x].back().second);
}
int Unite(int x, int y) {
t++;
x = Find(x), y = Find(y);
if (x != y) {
if (sz[x].back().second > sz[y].back().second) {
swap(x, y);
}
p[x].emplace_back(t, y);
sz[y].emplace_back(t, sz[y].back().second + sz[x].back().second);
if (deg[x].back().second > deg[y].back().second) {
deg[y].emplace_back(t, deg[x].back().second);
}
if (cycle[y].back().second == 0 && cycle[x].back().second == 1) {
cycle[y].emplace_back(t, 1);
}
return 1;
}
return 0;
}
int UpdateCycle(int x) {
x = Find(x);
if (cycle[x].back().second == 0) {
cycle[x].emplace_back(t, 1);
}
}
int UpdateDegree(int x, int v) {
x = Find(x);
if (v > deg[x].back().second) {
deg[x].emplace_back(t, v);
}
}
int Find(int x, int tt) {
assert(p[x].size() <= 2);
int pp = p[x][0].second;
if (p[x].size() > 1 && p[x][1].first <= tt) {
pp = p[x][1].second;
}
return pp == x ? x : Find(pp, tt);
}
int Degree(int x, int tt) {
int pos = upper_bound(begin(deg[x]), end(deg[x]), make_pair(tt, int(1e9))) - begin(deg[x]) - 1;
return deg[x][pos].second;
}
int Cycle(int x, int tt) {
int pos = upper_bound(begin(cycle[x]), end(cycle[x]), make_pair(tt, int(1e9))) - begin(cycle[x]) - 1;
return cycle[x][pos].second;
}
};
DisjointSet D;
vector<int> values;
bool Check(int x, int y, int m) {
x = D.Find(x, m), y = D.Find(y, m);
return x == y && (D.Degree(x, m) >= 3 || D.Cycle(x, m) == 1);
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
values = W;
sort(begin(values), end(values));
vector<array<int, 3>> E;
for (int i = 0; i < M; i++) {
E.push_back({W[i], U[i], V[i]});
}
sort(begin(E), end(E));
D = DisjointSet(N);
for (int i = 0; i < M; i++) {
static vector<int> deg(N);
deg[E[i][1]]++, deg[E[i][2]]++;
if (!D.Unite(E[i][1], E[i][2])) {
D.UpdateCycle(E[i][1]);
}
D.UpdateDegree(E[i][1], min(3, max(deg[E[i][1]], deg[E[i][2]])));
}
}
int getMinimumFuelCapacity(int X, int Y) {
int lo = 0, hi = int(values.size()) - 1;
if (!Check(X, Y, hi)) {
return -1;
}
while (lo < hi) {
int md = (lo + hi) / 2;
if (Check(X, Y, md)) {
hi = md;
} else {
lo = md + 1;
}
}
return values[lo];
}
Compilation message
swap.cpp: In member function 'int DisjointSet::UpdateCycle(int)':
swap.cpp:50:3: warning: no return statement in function returning non-void [-Wreturn-type]
50 | }
| ^
swap.cpp: In member function 'int DisjointSet::UpdateDegree(int, int)':
swap.cpp:56:3: warning: no return statement in function returning non-void [-Wreturn-type]
56 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
384 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
384 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
384 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
384 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
384 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
384 KB |
Execution killed with signal 11 |
