#include <time.h>
#include <cstdlib>
#include <stack>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <map>
#include <set>
#include <iterator>
#include <deque>
#include <queue>
#include <sstream>
#include <array>
#include <string>
#include <tuple>
#include <chrono>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <list>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <bitset>
#include "swap.h"
#include <cassert>
#include <cstdio>
using namespace std;
vector<int> g[200005];
pair<int, int> p[200005];
map<pair<int, int>, int> mp, pos;
set<pair<int, int>> st;
int x, y, mx;
bool ok = 0, ok1;
vector<int> A, B, C;
bool us[200005];
vector<int> ff[200005];
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
x = N;
y = M;
if(x - 1 != y) ok = 1;
for(int i = 0; i < M; i++){
int a = U[i] + 1, b = V[i] + 1, c = W[i];
if(a != 1) ok = 1;
mp[{a, b}] = c;
mp[{b, a}] = c;
pos[{a, b}] = i + 1;
pos[{b, a}] = i + 1;
ff[a].push_back(b);
ff[b].push_back(a);
st.insert({c, i + 1});
A.push_back(a);
B.push_back(b);
C.push_back(c);
}
for(int i = 1; i <= x; i++){
if(ff[i].size() > 2) ok1 = 1;
}
}
int kol = 0, kol1 = 0;
int dist[200005];
map<pair<int, int>, int> edge;
void dfs(int k){
us[k] = 1;
kol++;
for(int to : g[k]){
if(edge[{k, to}] == 0){
edge[{k, to}]++;
edge[{to, k}]++;
kol1++;
}
if(us[to]) continue;
dfs(to);
}
}
int getMinimumFuelCapacity(int X, int Y) {
if(!ok1){
if(x == y) return st.rbegin()->first;
else return -1;
}
if(ok){
X++;
Y++;
int L = 0, R = 1e9 + 1;
while(L + 1 < R){
int mid = (L + R) / 2;
kol = 0;
for(int i = 0; i <= x; i++){
g[i].clear();
us[i] = 0;
}
for(int i = 0; i < y; i++){
if(C[i] <= mid){
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
}
int kk = 0;
edge.clear();
kol1 = kol = 0;
dfs(X);
for(int i = 1; i <= x; i++)
if(us[i] == 1 && g[i].size() >= 3) kk++;
if(!us[Y]){
L = mid;
continue;
}
if(kol - 1 == kol1 && kk == 0){
L = mid;
continue;
}
R = mid;
continue;
}
if(R == 1000000001) return -1;
return R;
}
else{
X++;
Y++;
if(x <= 3)
return -1;
int mx = 0;
if(X != 1) mx = mp[{1, X}];
if(Y != 1) mx = max(mx, mp[{1, Y}]);
if(X != 1) st.erase({mp[{1, X}], pos[{1, X}]});
if(Y != 1) st.erase({mp[{1, Y}], pos[{1, Y}]});
pair<int, int> p = *st.begin();
st.erase(st.begin());
if(X != 1 && Y != 1){
st.insert(p);
if(X != 1) st.insert({mp[{1, X}], pos[{1, X}]});
if(Y != 1) st.insert({mp[{1, Y}], pos[{1, Y}]});
return max(mx, p.first);
}
else{
pair<int, int> p1 = *st.begin();
st.insert(p1);
st.insert(p);
if(X != 1) st.insert({mp[{1, X}], pos[{1, X}]});
if(Y != 1) st.insert({mp[{1, Y}], pos[{1, Y}]});
return max({mx, p.first, p1.first});
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12124 KB |
Output is correct |
2 |
Correct |
3 ms |
12124 KB |
Output is correct |
3 |
Correct |
3 ms |
12124 KB |
Output is correct |
4 |
Correct |
3 ms |
12124 KB |
Output is correct |
5 |
Correct |
4 ms |
12380 KB |
Output is correct |
6 |
Correct |
4 ms |
12380 KB |
Output is correct |
7 |
Correct |
4 ms |
12444 KB |
Output is correct |
8 |
Correct |
4 ms |
12376 KB |
Output is correct |
9 |
Correct |
250 ms |
40836 KB |
Output is correct |
10 |
Correct |
312 ms |
47044 KB |
Output is correct |
11 |
Correct |
333 ms |
46652 KB |
Output is correct |
12 |
Correct |
319 ms |
48448 KB |
Output is correct |
13 |
Correct |
319 ms |
48448 KB |
Output is correct |
14 |
Correct |
250 ms |
40764 KB |
Output is correct |
15 |
Correct |
374 ms |
49100 KB |
Output is correct |
16 |
Correct |
369 ms |
48192 KB |
Output is correct |
17 |
Correct |
385 ms |
50348 KB |
Output is correct |
18 |
Correct |
366 ms |
50260 KB |
Output is correct |
19 |
Correct |
64 ms |
21324 KB |
Output is correct |
20 |
Correct |
382 ms |
50328 KB |
Output is correct |
21 |
Correct |
339 ms |
49144 KB |
Output is correct |
22 |
Correct |
372 ms |
51652 KB |
Output is correct |
23 |
Correct |
393 ms |
51808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12124 KB |
Output is correct |
2 |
Correct |
3 ms |
12124 KB |
Output is correct |
3 |
Correct |
1147 ms |
49952 KB |
Output is correct |
4 |
Correct |
1119 ms |
51744 KB |
Output is correct |
5 |
Correct |
1256 ms |
50576 KB |
Output is correct |
6 |
Correct |
1171 ms |
51588 KB |
Output is correct |
7 |
Correct |
1217 ms |
51124 KB |
Output is correct |
8 |
Correct |
1123 ms |
49680 KB |
Output is correct |
9 |
Correct |
1122 ms |
50996 KB |
Output is correct |
10 |
Correct |
1101 ms |
49300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12124 KB |
Output is correct |
2 |
Correct |
3 ms |
12124 KB |
Output is correct |
3 |
Correct |
3 ms |
12124 KB |
Output is correct |
4 |
Correct |
3 ms |
12124 KB |
Output is correct |
5 |
Correct |
4 ms |
12380 KB |
Output is correct |
6 |
Correct |
4 ms |
12380 KB |
Output is correct |
7 |
Correct |
4 ms |
12444 KB |
Output is correct |
8 |
Correct |
4 ms |
12376 KB |
Output is correct |
9 |
Correct |
3 ms |
12120 KB |
Output is correct |
10 |
Correct |
23 ms |
12636 KB |
Output is correct |
11 |
Correct |
43 ms |
12636 KB |
Output is correct |
12 |
Correct |
45 ms |
12636 KB |
Output is correct |
13 |
Correct |
36 ms |
12636 KB |
Output is correct |
14 |
Correct |
33 ms |
12636 KB |
Output is correct |
15 |
Correct |
26 ms |
12632 KB |
Output is correct |
16 |
Correct |
47 ms |
12768 KB |
Output is correct |
17 |
Correct |
44 ms |
12796 KB |
Output is correct |
18 |
Correct |
37 ms |
12704 KB |
Output is correct |
19 |
Correct |
25 ms |
12632 KB |
Output is correct |
20 |
Correct |
43 ms |
12792 KB |
Output is correct |
21 |
Correct |
45 ms |
12636 KB |
Output is correct |
22 |
Correct |
17 ms |
12888 KB |
Output is correct |
23 |
Correct |
27 ms |
12376 KB |
Output is correct |
24 |
Correct |
27 ms |
12892 KB |
Output is correct |
25 |
Correct |
29 ms |
12892 KB |
Output is correct |
26 |
Correct |
57 ms |
13148 KB |
Output is correct |
27 |
Correct |
36 ms |
12636 KB |
Output is correct |
28 |
Correct |
33 ms |
13116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12120 KB |
Output is correct |
2 |
Correct |
3 ms |
12124 KB |
Output is correct |
3 |
Correct |
3 ms |
12124 KB |
Output is correct |
4 |
Correct |
3 ms |
12124 KB |
Output is correct |
5 |
Correct |
3 ms |
12124 KB |
Output is correct |
6 |
Correct |
4 ms |
12380 KB |
Output is correct |
7 |
Correct |
4 ms |
12380 KB |
Output is correct |
8 |
Correct |
4 ms |
12444 KB |
Output is correct |
9 |
Correct |
4 ms |
12376 KB |
Output is correct |
10 |
Correct |
250 ms |
40836 KB |
Output is correct |
11 |
Correct |
312 ms |
47044 KB |
Output is correct |
12 |
Correct |
333 ms |
46652 KB |
Output is correct |
13 |
Correct |
319 ms |
48448 KB |
Output is correct |
14 |
Correct |
319 ms |
48448 KB |
Output is correct |
15 |
Correct |
23 ms |
12636 KB |
Output is correct |
16 |
Correct |
43 ms |
12636 KB |
Output is correct |
17 |
Correct |
45 ms |
12636 KB |
Output is correct |
18 |
Correct |
36 ms |
12636 KB |
Output is correct |
19 |
Correct |
33 ms |
12636 KB |
Output is correct |
20 |
Correct |
26 ms |
12632 KB |
Output is correct |
21 |
Correct |
47 ms |
12768 KB |
Output is correct |
22 |
Correct |
44 ms |
12796 KB |
Output is correct |
23 |
Correct |
37 ms |
12704 KB |
Output is correct |
24 |
Correct |
25 ms |
12632 KB |
Output is correct |
25 |
Correct |
43 ms |
12792 KB |
Output is correct |
26 |
Correct |
45 ms |
12636 KB |
Output is correct |
27 |
Correct |
17 ms |
12888 KB |
Output is correct |
28 |
Correct |
27 ms |
12376 KB |
Output is correct |
29 |
Correct |
27 ms |
12892 KB |
Output is correct |
30 |
Correct |
29 ms |
12892 KB |
Output is correct |
31 |
Correct |
57 ms |
13148 KB |
Output is correct |
32 |
Correct |
36 ms |
12636 KB |
Output is correct |
33 |
Correct |
33 ms |
13116 KB |
Output is correct |
34 |
Correct |
165 ms |
18992 KB |
Output is correct |
35 |
Execution timed out |
2052 ms |
71116 KB |
Time limit exceeded |
36 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12124 KB |
Output is correct |
2 |
Correct |
3 ms |
12124 KB |
Output is correct |
3 |
Correct |
3 ms |
12124 KB |
Output is correct |
4 |
Correct |
3 ms |
12124 KB |
Output is correct |
5 |
Correct |
4 ms |
12380 KB |
Output is correct |
6 |
Correct |
4 ms |
12380 KB |
Output is correct |
7 |
Correct |
4 ms |
12444 KB |
Output is correct |
8 |
Correct |
4 ms |
12376 KB |
Output is correct |
9 |
Correct |
250 ms |
40836 KB |
Output is correct |
10 |
Correct |
312 ms |
47044 KB |
Output is correct |
11 |
Correct |
333 ms |
46652 KB |
Output is correct |
12 |
Correct |
319 ms |
48448 KB |
Output is correct |
13 |
Correct |
319 ms |
48448 KB |
Output is correct |
14 |
Correct |
250 ms |
40764 KB |
Output is correct |
15 |
Correct |
374 ms |
49100 KB |
Output is correct |
16 |
Correct |
369 ms |
48192 KB |
Output is correct |
17 |
Correct |
385 ms |
50348 KB |
Output is correct |
18 |
Correct |
366 ms |
50260 KB |
Output is correct |
19 |
Correct |
1147 ms |
49952 KB |
Output is correct |
20 |
Correct |
1119 ms |
51744 KB |
Output is correct |
21 |
Correct |
1256 ms |
50576 KB |
Output is correct |
22 |
Correct |
1171 ms |
51588 KB |
Output is correct |
23 |
Correct |
1217 ms |
51124 KB |
Output is correct |
24 |
Correct |
1123 ms |
49680 KB |
Output is correct |
25 |
Correct |
1122 ms |
50996 KB |
Output is correct |
26 |
Correct |
1101 ms |
49300 KB |
Output is correct |
27 |
Correct |
23 ms |
12636 KB |
Output is correct |
28 |
Correct |
43 ms |
12636 KB |
Output is correct |
29 |
Correct |
45 ms |
12636 KB |
Output is correct |
30 |
Correct |
36 ms |
12636 KB |
Output is correct |
31 |
Correct |
33 ms |
12636 KB |
Output is correct |
32 |
Correct |
26 ms |
12632 KB |
Output is correct |
33 |
Correct |
47 ms |
12768 KB |
Output is correct |
34 |
Correct |
44 ms |
12796 KB |
Output is correct |
35 |
Correct |
37 ms |
12704 KB |
Output is correct |
36 |
Correct |
165 ms |
18992 KB |
Output is correct |
37 |
Execution timed out |
2052 ms |
71116 KB |
Time limit exceeded |
38 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12120 KB |
Output is correct |
2 |
Correct |
3 ms |
12124 KB |
Output is correct |
3 |
Correct |
3 ms |
12124 KB |
Output is correct |
4 |
Correct |
3 ms |
12124 KB |
Output is correct |
5 |
Correct |
3 ms |
12124 KB |
Output is correct |
6 |
Correct |
4 ms |
12380 KB |
Output is correct |
7 |
Correct |
4 ms |
12380 KB |
Output is correct |
8 |
Correct |
4 ms |
12444 KB |
Output is correct |
9 |
Correct |
4 ms |
12376 KB |
Output is correct |
10 |
Correct |
250 ms |
40836 KB |
Output is correct |
11 |
Correct |
312 ms |
47044 KB |
Output is correct |
12 |
Correct |
333 ms |
46652 KB |
Output is correct |
13 |
Correct |
319 ms |
48448 KB |
Output is correct |
14 |
Correct |
319 ms |
48448 KB |
Output is correct |
15 |
Correct |
250 ms |
40764 KB |
Output is correct |
16 |
Correct |
374 ms |
49100 KB |
Output is correct |
17 |
Correct |
369 ms |
48192 KB |
Output is correct |
18 |
Correct |
385 ms |
50348 KB |
Output is correct |
19 |
Correct |
366 ms |
50260 KB |
Output is correct |
20 |
Correct |
1147 ms |
49952 KB |
Output is correct |
21 |
Correct |
1119 ms |
51744 KB |
Output is correct |
22 |
Correct |
1256 ms |
50576 KB |
Output is correct |
23 |
Correct |
1171 ms |
51588 KB |
Output is correct |
24 |
Correct |
1217 ms |
51124 KB |
Output is correct |
25 |
Correct |
1123 ms |
49680 KB |
Output is correct |
26 |
Correct |
1122 ms |
50996 KB |
Output is correct |
27 |
Correct |
1101 ms |
49300 KB |
Output is correct |
28 |
Correct |
23 ms |
12636 KB |
Output is correct |
29 |
Correct |
43 ms |
12636 KB |
Output is correct |
30 |
Correct |
45 ms |
12636 KB |
Output is correct |
31 |
Correct |
36 ms |
12636 KB |
Output is correct |
32 |
Correct |
33 ms |
12636 KB |
Output is correct |
33 |
Correct |
26 ms |
12632 KB |
Output is correct |
34 |
Correct |
47 ms |
12768 KB |
Output is correct |
35 |
Correct |
44 ms |
12796 KB |
Output is correct |
36 |
Correct |
37 ms |
12704 KB |
Output is correct |
37 |
Correct |
165 ms |
18992 KB |
Output is correct |
38 |
Execution timed out |
2052 ms |
71116 KB |
Time limit exceeded |
39 |
Halted |
0 ms |
0 KB |
- |