#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 25;
int t[MAXN], n, m;
array <int, 3> edges[MAXN];
int deg[MAXN];
vector <int> sub[MAXN]; int par[MAXN];
bool ok[MAXN];
vector <array <int, 3>> times[MAXN];
int sum = 0;
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[i] = {u[i], v[i], w[i]};
for (int i = 0; i < m; i++) t[i] = i;
sort(t, t + m, [&] (int &x, int &y) { return edges[x][2] < edges[y][2]; });
for (int i = 0; i < n; i++) {
sub[i].push_back(i);
par[i] = i;
times[i].push_back({-1, i, 0}); sum++;assert(sum <= 1e7);
}
for (int i = 0; i < m; i++) {
int a = edges[t[i]][0], b = edges[t[i]][1];
if (par[a] == par[b]) {
if (ok[par[a]]) {
deg[a]++; deg[b]++;
continue;
}
ok[par[a]] = 1;
for (auto j : sub[par[a]]) {
times[j].push_back({i, par[a], 1}); sum++;assert(sum <= 1e7);
}
deg[a]++; deg[b]++;
continue;
}
if (sub[par[a]].size() > sub[par[b]].size()) swap(a, b);
bool flag = ok[par[a]] || ok[par[b]];
flag |= deg[a] > 1 || deg[b] > 1;
if (!flag) {
int l = par[a];
for (auto j : sub[l]) {
times[j].push_back({i, par[b], 0}); sum++;assert(sum <= 1e7);
par[j] = par[b];
sub[par[b]].push_back(j);
}
sub[l].clear();
deg[a]++; deg[b]++;
continue;
}
if (!ok[par[b]]) {
ok[par[b]] = 1;
for (auto j : sub[par[b]]) {
times[j].push_back({i, par[b], 1}); sum++; assert(sum <= 1e7);
}
}
int l = par[a];
for (auto j : sub[l]) {
times[j].push_back({i, par[b], 1}); sum++;assert(sum <= 1e7);
par[j] = par[b];
sub[par[b]].push_back(j);
}
sub[l].clear();
deg[a]++; deg[b]++;
}
}
int getMinimumFuelCapacity (int x, int y) {
int l = 0, r = m - 1, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
array <int, 3> ff = {mid + 1, (int)-1e9, (int)-1e9};
auto g = lower_bound(times[x].begin(), times[x].end(), ff) - times[x].begin();
auto h = lower_bound(times[y].begin(), times[y].end(), ff) - times[y].begin();
g--; h--;
if (times[x][g][1] != times[y][h][1]) {
l = mid + 1; continue;
}
if (!times[x][g][2] || !times[y][h][2]) {
l = mid + 1;
} else {
r = mid - 1; ans = mid;
}
}
return ans == -1 ? -1 : edges[t[ans]][2];
}
int main () {
init(5, 6, {0, 0, 1, 1, 1, 2}, {1, 2, 2, 3, 4, 3}, {4, 4, 1, 2, 10, 3});
cout << getMinimumFuelCapacity(1, 2) << " " << getMinimumFuelCapacity(2, 4) << " " << getMinimumFuelCapacity(0, 1) << '\n';
}
Compilation message
/usr/bin/ld: /tmp/ccOcC20j.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc1aarWj.o:swap.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
