#include<bits/stdc++.h>
using namespace std;
struct dsu {
vector<int> p;
dsu(int n) {
p.resize(n, -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;
}
};
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;
}
int getMinimumFuelCapacity(int x, int y) {
auto test = [&](int val) {
for (int i = 0; i < n; i++) g[i].clear();
dsu ds(n);
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]));
ds.unite(get<1>(edges[i]), get<2>(edges[i]));
}
}
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]);
return (d[0][y] + 1 < -ds.p[ds.get(y)]);
/*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 = 4, M = 3;
vector<int> U = {0, 0, 0};
vector<int> V = {1, 2, 3};
vector<int> W = {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:99:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
99 | int mid = l + r >> 1;
| ~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 3 |
Execution timed out |
2074 ms |
11996 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
