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>
constexpr int N = 1e5;
int n, m;
std::vector<int> e[N];
std::vector<int> U, V, W, v;
std::vector<int> p;
std::vector<bool> vis;
bool have;
void init(int n, int m, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
::U = U;
::V = V;
::W = W;
::n = n;
::m = m;
v = W;
sort(v.begin(), v.end());
}
void dfs(int u, int P)
{
p[u] = P;
vis[u] = true;
if (e[u].size() > 2) have = true;
for (auto v : e[u])
if (!vis[v])
dfs(v, u);
}
bool check(int X, int Y, int mid)
{
for (int i = 0; i < n; i++) e[i].clear();
for (int i = 0; i < m; i++)
{
if (W[i] <= mid)
{
e[U[i]].emplace_back(V[i]);
e[V[i]].emplace_back(U[i]);
}
}
p.assign(n, -1);
vis.assign(n, false);
have = false;
dfs(X, -1);
if (p[Y] == -1)
return false;
if (have)
return true;
int y = Y;
std::vector<int> got;
y = p[y];
while (y != -1 && p[y] != -1)
{
got.push_back(y);
y = p[y];
}
std::vector<bool> bad(n, false);
for (auto x : got) bad[x] = true;
for (int i = 0; i < n; i++) e[i].clear();
for (int i = 0; i < m; i++)
{
if (W[i] <= mid && !bad[U[i]] && !bad[V[i]])
{
e[U[i]].emplace_back(V[i]);
e[V[i]].emplace_back(U[i]);
}
}
if (!got.size())
{
e[X].erase(find(e[X].begin(), e[X].end(), Y));
e[Y].erase(find(e[Y].begin(), e[Y].end(), X));
}
p.assign(n, -1);
vis.assign(n, false);
dfs(X, -1);
if (p[Y] != -1)
return true;
return false;
}
int getMinimumFuelCapacity(int X, int Y)
{
int l = 0, r = v.size() - 1;
while (l < r)
{
int mid = (l + r) / 2;
if (check(X, Y, v[mid])) r = mid;
else l = mid;
}
if (r == v.size()) return -1;
return v[r];
}
Compilation message (stderr)
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:103:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | if (r == v.size()) 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... |