#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
#include "swap.h"
const int MAX = 1e5 + 5;
int N, M;
vector<ii> adj[MAX]; // {vertex, dist}
void init(int N_g, int M_g, vi U_g, vi V_g, vi W_g) {
N = N_g;
M = M_g;
for (int i = 0; i < M; i++) {
adj[U_g[i]].pb({V_g[i], W_g[i]});
adj[V_g[i]].pb({U_g[i], W_g[i]});
}
}
bool check(int cut, int X, int Y) {
vi adjc[N];
for (int i = 0; i < N; i++) {
for (ii p : adj[i]) {
if (p.se <= cut)
adjc[i].pb(p.fi);
}
}
vector<bool> vis(N, false);
queue<int> q;
q.push(X);
vis[X] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int y : adjc[x]) {
if (!vis[y]) {
q.push(y);
vis[y] = true;
}
}
}
if (!vis[Y])
return false;
int cnte = 0; // number of edges
int sz = 0; // number of vertices
for (int i = 0; i < N; i++) {
cnte += adjc[i].size();
if (adjc[i].size() >= 1)
sz++;
}
cnte /= 2;
// cout<<"sz, cnte: "<<sz<<" "<<cnte<<endl;
if (cnte > sz - 1) // has a cycle
return true;
for (int i = 0; i < N; i++) {
if (adjc[i].size() >= 3)
return true;
}
return false;
}
int getMinimumFuelCapacity(int X, int Y) {
// cout<<check(3, X, Y)<<endl;
int low = 0;
int high = 1e9 + 5;
int ans = -1; // minimum so can pass
while (low <= high) { // false, false, false, true, true, true
int mid = (low + high) / 2;
if (check(mid, X, Y)) {
ans = mid;
high = mid - 1;
}
else {
low = mid + 1;
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2648 KB |
Output is correct |
4 |
Correct |
4 ms |
2652 KB |
Output is correct |
5 |
Correct |
7 ms |
2856 KB |
Output is correct |
6 |
Correct |
8 ms |
2884 KB |
Output is correct |
7 |
Correct |
8 ms |
2904 KB |
Output is correct |
8 |
Correct |
9 ms |
2652 KB |
Output is correct |
9 |
Correct |
357 ms |
12368 KB |
Output is correct |
10 |
Correct |
832 ms |
14220 KB |
Output is correct |
11 |
Correct |
1014 ms |
13816 KB |
Output is correct |
12 |
Correct |
1055 ms |
14524 KB |
Output is correct |
13 |
Correct |
1202 ms |
14516 KB |
Output is correct |
14 |
Execution timed out |
2025 ms |
12468 KB |
Time limit exceeded |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Execution timed out |
2058 ms |
19724 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2648 KB |
Output is correct |
4 |
Correct |
4 ms |
2652 KB |
Output is correct |
5 |
Correct |
7 ms |
2856 KB |
Output is correct |
6 |
Correct |
8 ms |
2884 KB |
Output is correct |
7 |
Correct |
8 ms |
2904 KB |
Output is correct |
8 |
Correct |
9 ms |
2652 KB |
Output is correct |
9 |
Correct |
1 ms |
2648 KB |
Output is correct |
10 |
Correct |
7 ms |
2648 KB |
Output is correct |
11 |
Correct |
8 ms |
2796 KB |
Output is correct |
12 |
Correct |
15 ms |
2896 KB |
Output is correct |
13 |
Correct |
7 ms |
2652 KB |
Output is correct |
14 |
Correct |
7 ms |
2876 KB |
Output is correct |
15 |
Incorrect |
8 ms |
2652 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2648 KB |
Output is correct |
2 |
Correct |
2 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2648 KB |
Output is correct |
5 |
Correct |
4 ms |
2652 KB |
Output is correct |
6 |
Correct |
7 ms |
2856 KB |
Output is correct |
7 |
Correct |
8 ms |
2884 KB |
Output is correct |
8 |
Correct |
8 ms |
2904 KB |
Output is correct |
9 |
Correct |
9 ms |
2652 KB |
Output is correct |
10 |
Correct |
357 ms |
12368 KB |
Output is correct |
11 |
Correct |
832 ms |
14220 KB |
Output is correct |
12 |
Correct |
1014 ms |
13816 KB |
Output is correct |
13 |
Correct |
1055 ms |
14524 KB |
Output is correct |
14 |
Correct |
1202 ms |
14516 KB |
Output is correct |
15 |
Correct |
7 ms |
2648 KB |
Output is correct |
16 |
Correct |
8 ms |
2796 KB |
Output is correct |
17 |
Correct |
15 ms |
2896 KB |
Output is correct |
18 |
Correct |
7 ms |
2652 KB |
Output is correct |
19 |
Correct |
7 ms |
2876 KB |
Output is correct |
20 |
Incorrect |
8 ms |
2652 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2648 KB |
Output is correct |
4 |
Correct |
4 ms |
2652 KB |
Output is correct |
5 |
Correct |
7 ms |
2856 KB |
Output is correct |
6 |
Correct |
8 ms |
2884 KB |
Output is correct |
7 |
Correct |
8 ms |
2904 KB |
Output is correct |
8 |
Correct |
9 ms |
2652 KB |
Output is correct |
9 |
Correct |
357 ms |
12368 KB |
Output is correct |
10 |
Correct |
832 ms |
14220 KB |
Output is correct |
11 |
Correct |
1014 ms |
13816 KB |
Output is correct |
12 |
Correct |
1055 ms |
14524 KB |
Output is correct |
13 |
Correct |
1202 ms |
14516 KB |
Output is correct |
14 |
Execution timed out |
2025 ms |
12468 KB |
Time limit exceeded |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2648 KB |
Output is correct |
2 |
Correct |
2 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2648 KB |
Output is correct |
5 |
Correct |
4 ms |
2652 KB |
Output is correct |
6 |
Correct |
7 ms |
2856 KB |
Output is correct |
7 |
Correct |
8 ms |
2884 KB |
Output is correct |
8 |
Correct |
8 ms |
2904 KB |
Output is correct |
9 |
Correct |
9 ms |
2652 KB |
Output is correct |
10 |
Correct |
357 ms |
12368 KB |
Output is correct |
11 |
Correct |
832 ms |
14220 KB |
Output is correct |
12 |
Correct |
1014 ms |
13816 KB |
Output is correct |
13 |
Correct |
1055 ms |
14524 KB |
Output is correct |
14 |
Correct |
1202 ms |
14516 KB |
Output is correct |
15 |
Execution timed out |
2025 ms |
12468 KB |
Time limit exceeded |
16 |
Halted |
0 ms |
0 KB |
- |