#include "swap.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
struct dsu {
vector<int> fa, sz, mx_deg;
dsu(int n) {
fa.resize(n + 10);
iota(fa.begin(), fa.end(), 0);
sz.assign(n + 10, 1);
mx_deg.assign(n + 10, 0);
}
int find(int x) {
while (x != fa[x]) x = fa[x] = fa[fa[x]];
return x;
}
bool merge(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return false;
if (sz[py] > sz[px]) swap(px, py);
sz[px] += sz[py]; fa[py] = px;
mx_deg[px] = max(mx_deg[px], mx_deg[py]);
return true;
}
bool same(int x, int y) {
int px = find(x), py = find(y);
return px == py;
}
};
vector<pair<int, pair<int, int>>> edges;
int n;
void init(int _N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = _N;
for (int i = 0; i < M; i++)
edges.push_back(make_pair(W[i], make_pair(U[i], V[i])));
sort(edges.begin(), edges.end());
}
int getMinimumFuelCapacity(int X, int Y) {
// cout << "++++++++++++++++\n";
bool flag = true;
dsu D(n);
vector<int> deg(n);
for (int i = 0; i < edges.size(); i++) {
int w = edges[i].first;
int u = edges[i].second.first, v = edges[i].second.second;
// cout << w << ' ' << u << ' ' << v << '\n';
for (int t = 0; t < 2; t++) {
if (!flag && X != u && D.same(X, u) && D.same(X, Y) && D.same(u, Y)) return w;
swap(u, v);
}
D.merge(u, v);
deg[u]++; deg[v]++;
if (deg[u] >= 3) {
D.mx_deg[D.find(u)] = 3;
}
if (deg[v] >= 3) {
D.mx_deg[D.find(v)] = 3;
}
if (D.mx_deg[D.find(X)] >= 3 && D.same(X, Y)) return w;
if (D.same(X, Y)) {
flag = false;
continue;
}
}
if (D.mx_deg[D.find(X)] >= 3 && D.same(X, Y)) return edges.back().first;
return -1;
}
#include "grader.cpp"
Compilation message
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for (int i = 0; i < edges.size(); i++) {
| ~~^~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cc6M6bbt.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccyKhSCr.o:swap.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
