#include<bits/stdc++.h>
using namespace std;
struct dsu {
vector<int> p;
dsu() {
}
void resize(int n) {
p.resize(n, -1);
}
void clear() {
for (auto&x : p) x = -1;
}
int get(int x) {
return p[x] < 0 ? x : p[x] = get(p[x]);
}
bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
if (p[x] < p[y]) swap(x, y);
p[y] += p[x];
p[x] = y;
return true;
}
return false;
}
}ds;
const int N = 1e5 + 3;
vector<tuple<int,int,int>> edges;
int n, m;
vector<int> g[N];
void init(int N, int M, vector<int> u, vector<int> v, vector<int> w) {
for (int i = 0; i < M; i++) {
edges.emplace_back(w[i], u[i], v[i]);
}
n = N;
m = M;
ds.resize(N);
}
int getMinimumFuelCapacity(int x, int y) {
auto test = [&](int val) {
for (int i = 0; i < n; i++) g[i].clear();
for (int i = 0; i < m; i++) {
if (get<0>(edges[i]) <= val) {
g[get<1>(edges[i])].push_back(get<2>(edges[i]));
g[get<2>(edges[i])].push_back(get<1>(edges[i]));
}
}
vector<int> cnt(n, -1);
function<int(int, int)> dfs = [&](int v, int p) {
if (cnt[v] != -1) return cnt[v];
if (v == y) return cnt[v] = 1;
cnt[v] = 0;
for (auto&u : g[v]) {
if (u != p) {
int add = dfs(u, v);
cnt[v] = min(2, dfs(u, v) + cnt[v]);
if (cnt[v] == 1 && add == 0) cnt[v] = 2;
if (cnt[v] == 2) break;
}
}
return cnt[2];
};
return (dfs(x, x) == 1);
/*vector<vector<int>> d(2, vector<int> (n));
auto dijkstra = [&](int s, vector<int>& d) {
for (int i = 0; i < n; i++) d[i] = (int) 1e9;
d[s] = 0;
deque<int> q = {s};
while (!q.empty()) {
int v = q.front(); q.pop_front();
for (auto&u : g[v]) {
if (d[u] > d[v] + 1) {
d[u] = d[v] + 1;
q.push_back(u);
}
}
}
};
dijkstra(x, d[0]);
dijkstra(y, d[1]);
int cnt = 0;
for (int i = 0; i < n; i++) if (d[0][i] != (int) 1e9) ++cnt;
return (d[0][y] + 1 < cnt);*/
/*dijkstra(y, d[1]);
vector<bool> precious(n);
for (int i = 0; i < n; i++) precious[i] = !(d[0][i] + d[1][i] == d[0][y]);
vector<int> can(2 * n);
can[x] = 1;
deque<int> q = {x};
while (!q.empty()) {
int v = q.front(); q.pop_front();
if (v % n == y) continue;
int type = v / n;
bool flag = false;
for (auto&u : g[v % n]) {
flag |= precious[u];
if (d[0][v % n] > d[0][u]) continue;
if (!type && can[u] && !can[u + n]) {
can[u + n] = 1;
q.push_back(u + n);
}
if (!can[u + type * n]) {
can[u + type * n] = 1;
q.push_back(u + type * n);
}
}
if (flag && !type && !can[v + n]) {
can[v + n] = 1;
q.push_back(v + n);
}
}
return can[n + y];*/
};
int l = 0, r = (int)1e9;
while (l <= r) {
int mid = l + r >> 1;
if (test(mid)) r = mid - 1;
else l = mid + 1;
}
if (l == (int) 1e9 + 1) l = -1;
return l;
}
/*
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int N = 5, M = 4;
vector<int> U = {0, 0, 0, 0};
vector<int> V = {1, 2, 3, 4};
vector<int> W = {4, 1, 2, 3};
init(N, M, U, V, W);
int q = 1;
while (q--) {
int x, y;
cin >> x >> y;
cout << getMinimumFuelCapacity(x, y) << "\n" << flush;
}
}*/
Compilation message
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:122:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
122 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
