#include "swap.h"
#include "bits/stdc++.h"
#include <vector>
using namespace std;
using ll = long long;
const int MAXN = 1e5+5;
vector < vector< pair<ll, ll> > > adj(MAXN);
int sum_dist = 0;
int dist[MAXN];
int par[MAXN], sz[MAXN], edge_sz[MAXN], max_sz[MAXN], cnt[MAXN];
int max_ed = 0, u_max;
int n, m;
vector < pair<int, pair<int, int> > > edges;
int find(int v)
{
if(par[v] == v)
return v;
return par[v] = find(par[v]);
}
void merge(int a, int b)
{
int maxi = max(cnt[a], cnt[b]);
a = find(a), b = find(b);
if(a == b) {
edge_sz[a]++;
max_sz[a] = max(max_sz[a], maxi);
return;
}
if(sz[a] < sz[b])
swap(a, b);
par[b] = a;
sz[a] += sz[b];
edge_sz[a]++;
edge_sz[a] += edge_sz[b];
max_sz[a] = max(max_sz[a], max(max_sz[b], maxi));
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
m = M;
n = N;
for(int i = 0; i < M; i++)
{
adj[U[i]].push_back({W[i], V[i]});
adj[V[i]].push_back({W[i], U[i]});
dist[V[i]] = W[i]; // for sub 2
edges.push_back({W[i], {U[i], V[i]}});
u_max = max(u_max, U[i]);
sum_dist = max(sum_dist, W[i]);
}
sort(edges.begin(), edges.end());
for(int i = 0; i < N; i++)
{
sort(adj[i].begin(), adj[i].end());
max_ed = max(max_ed, (int)adj[i].size());
}
}
int getMinimumFuelCapacity(int X, int Y) {
if(max_ed <= 2) // Sub 1
{
if(m == n - 1)
return -1;
else
return sum_dist;
}
if(u_max == 0) // Sub 2
{
if(X > Y)
swap(X, Y);
ll sum = max(dist[X], dist[Y]);
if(X != 0) {
sum = max(sum, (adj[0][0].second != X && adj[0][0].second != Y) ? adj[0][0].first : ((adj[0][1].second != X && adj[0][1].second != Y) ? adj[0][1].first : adj[0][2].first));
} else
{
sum = max(sum, (adj[0][0].second != Y ? max(adj[0][0].first, adj[0][1].second != Y ? adj[0][1].first : adj[0][2].first) : max(adj[0][1].first, adj[0][2].first)));
}
return sum;
}
//Sub 3, 4
for(int i = 0; i < n; i++)
{
cnt[i] = 0;
edge_sz[i] = max_sz[i] = 0;
sz[i] = 1;
par[i] = i;
}
for(pair<int, pair<int, int> > edge : edges)
{
cnt[edge.second.first]++;
cnt[edge.second.second]++;
merge(edge.second.first, edge.second.second);
if(find(X) == find(Y))
{
int curr = find(X);
if(edge_sz[curr] >= sz[curr] || max_sz[curr] > 2)
return edge.first;
}
}
return -1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
3 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2672 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2772 KB |
Output is correct |
9 |
Correct |
49 ms |
9808 KB |
Output is correct |
10 |
Correct |
63 ms |
11388 KB |
Output is correct |
11 |
Correct |
72 ms |
11244 KB |
Output is correct |
12 |
Correct |
70 ms |
11788 KB |
Output is correct |
13 |
Correct |
82 ms |
11816 KB |
Output is correct |
14 |
Correct |
68 ms |
10036 KB |
Output is correct |
15 |
Correct |
122 ms |
13196 KB |
Output is correct |
16 |
Correct |
118 ms |
13068 KB |
Output is correct |
17 |
Correct |
132 ms |
13572 KB |
Output is correct |
18 |
Correct |
130 ms |
13580 KB |
Output is correct |
19 |
Correct |
53 ms |
7556 KB |
Output is correct |
20 |
Correct |
114 ms |
14408 KB |
Output is correct |
21 |
Correct |
133 ms |
14436 KB |
Output is correct |
22 |
Correct |
141 ms |
14996 KB |
Output is correct |
23 |
Correct |
126 ms |
14988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
111 ms |
13780 KB |
Output is correct |
4 |
Correct |
108 ms |
14040 KB |
Output is correct |
5 |
Correct |
109 ms |
14108 KB |
Output is correct |
6 |
Correct |
112 ms |
13956 KB |
Output is correct |
7 |
Correct |
117 ms |
14192 KB |
Output is correct |
8 |
Correct |
130 ms |
13716 KB |
Output is correct |
9 |
Correct |
107 ms |
13944 KB |
Output is correct |
10 |
Correct |
126 ms |
13684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
3 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2672 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2772 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
4 ms |
2772 KB |
Output is correct |
11 |
Correct |
3 ms |
2772 KB |
Output is correct |
12 |
Correct |
4 ms |
2772 KB |
Output is correct |
13 |
Correct |
3 ms |
2772 KB |
Output is correct |
14 |
Correct |
3 ms |
2752 KB |
Output is correct |
15 |
Correct |
2 ms |
2772 KB |
Output is correct |
16 |
Correct |
2 ms |
2772 KB |
Output is correct |
17 |
Correct |
2 ms |
2772 KB |
Output is correct |
18 |
Correct |
2 ms |
2772 KB |
Output is correct |
19 |
Correct |
2 ms |
2772 KB |
Output is correct |
20 |
Correct |
2 ms |
2772 KB |
Output is correct |
21 |
Correct |
2 ms |
2772 KB |
Output is correct |
22 |
Correct |
3 ms |
2772 KB |
Output is correct |
23 |
Correct |
3 ms |
2644 KB |
Output is correct |
24 |
Correct |
2 ms |
2772 KB |
Output is correct |
25 |
Correct |
3 ms |
2804 KB |
Output is correct |
26 |
Correct |
3 ms |
2896 KB |
Output is correct |
27 |
Correct |
2 ms |
2812 KB |
Output is correct |
28 |
Correct |
3 ms |
2900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
3 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2672 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2772 KB |
Output is correct |
10 |
Correct |
49 ms |
9808 KB |
Output is correct |
11 |
Correct |
63 ms |
11388 KB |
Output is correct |
12 |
Correct |
72 ms |
11244 KB |
Output is correct |
13 |
Correct |
70 ms |
11788 KB |
Output is correct |
14 |
Correct |
82 ms |
11816 KB |
Output is correct |
15 |
Correct |
4 ms |
2772 KB |
Output is correct |
16 |
Correct |
3 ms |
2772 KB |
Output is correct |
17 |
Correct |
4 ms |
2772 KB |
Output is correct |
18 |
Correct |
3 ms |
2772 KB |
Output is correct |
19 |
Correct |
3 ms |
2752 KB |
Output is correct |
20 |
Correct |
2 ms |
2772 KB |
Output is correct |
21 |
Correct |
2 ms |
2772 KB |
Output is correct |
22 |
Correct |
2 ms |
2772 KB |
Output is correct |
23 |
Correct |
2 ms |
2772 KB |
Output is correct |
24 |
Correct |
2 ms |
2772 KB |
Output is correct |
25 |
Correct |
2 ms |
2772 KB |
Output is correct |
26 |
Correct |
2 ms |
2772 KB |
Output is correct |
27 |
Correct |
3 ms |
2772 KB |
Output is correct |
28 |
Correct |
3 ms |
2644 KB |
Output is correct |
29 |
Correct |
2 ms |
2772 KB |
Output is correct |
30 |
Correct |
3 ms |
2804 KB |
Output is correct |
31 |
Correct |
3 ms |
2896 KB |
Output is correct |
32 |
Correct |
2 ms |
2812 KB |
Output is correct |
33 |
Correct |
3 ms |
2900 KB |
Output is correct |
34 |
Correct |
9 ms |
4104 KB |
Output is correct |
35 |
Correct |
78 ms |
12532 KB |
Output is correct |
36 |
Correct |
82 ms |
12576 KB |
Output is correct |
37 |
Correct |
86 ms |
12468 KB |
Output is correct |
38 |
Correct |
112 ms |
12428 KB |
Output is correct |
39 |
Correct |
81 ms |
12436 KB |
Output is correct |
40 |
Correct |
79 ms |
11616 KB |
Output is correct |
41 |
Correct |
91 ms |
12588 KB |
Output is correct |
42 |
Correct |
84 ms |
12588 KB |
Output is correct |
43 |
Correct |
72 ms |
12576 KB |
Output is correct |
44 |
Correct |
96 ms |
12728 KB |
Output is correct |
45 |
Correct |
128 ms |
19388 KB |
Output is correct |
46 |
Correct |
103 ms |
14344 KB |
Output is correct |
47 |
Correct |
77 ms |
14428 KB |
Output is correct |
48 |
Correct |
101 ms |
15456 KB |
Output is correct |
49 |
Correct |
96 ms |
20824 KB |
Output is correct |
50 |
Correct |
91 ms |
15836 KB |
Output is correct |
51 |
Correct |
91 ms |
16736 KB |
Output is correct |
52 |
Correct |
124 ms |
20472 KB |
Output is correct |
53 |
Correct |
178 ms |
22324 KB |
Output is correct |
54 |
Correct |
160 ms |
24360 KB |
Output is correct |
55 |
Correct |
84 ms |
14456 KB |
Output is correct |
56 |
Correct |
173 ms |
21592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
3 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2672 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2772 KB |
Output is correct |
9 |
Correct |
49 ms |
9808 KB |
Output is correct |
10 |
Correct |
63 ms |
11388 KB |
Output is correct |
11 |
Correct |
72 ms |
11244 KB |
Output is correct |
12 |
Correct |
70 ms |
11788 KB |
Output is correct |
13 |
Correct |
82 ms |
11816 KB |
Output is correct |
14 |
Correct |
68 ms |
10036 KB |
Output is correct |
15 |
Correct |
122 ms |
13196 KB |
Output is correct |
16 |
Correct |
118 ms |
13068 KB |
Output is correct |
17 |
Correct |
132 ms |
13572 KB |
Output is correct |
18 |
Correct |
130 ms |
13580 KB |
Output is correct |
19 |
Correct |
111 ms |
13780 KB |
Output is correct |
20 |
Correct |
108 ms |
14040 KB |
Output is correct |
21 |
Correct |
109 ms |
14108 KB |
Output is correct |
22 |
Correct |
112 ms |
13956 KB |
Output is correct |
23 |
Correct |
117 ms |
14192 KB |
Output is correct |
24 |
Correct |
130 ms |
13716 KB |
Output is correct |
25 |
Correct |
107 ms |
13944 KB |
Output is correct |
26 |
Correct |
126 ms |
13684 KB |
Output is correct |
27 |
Correct |
4 ms |
2772 KB |
Output is correct |
28 |
Correct |
3 ms |
2772 KB |
Output is correct |
29 |
Correct |
4 ms |
2772 KB |
Output is correct |
30 |
Correct |
3 ms |
2772 KB |
Output is correct |
31 |
Correct |
3 ms |
2752 KB |
Output is correct |
32 |
Correct |
2 ms |
2772 KB |
Output is correct |
33 |
Correct |
2 ms |
2772 KB |
Output is correct |
34 |
Correct |
2 ms |
2772 KB |
Output is correct |
35 |
Correct |
2 ms |
2772 KB |
Output is correct |
36 |
Correct |
9 ms |
4104 KB |
Output is correct |
37 |
Correct |
78 ms |
12532 KB |
Output is correct |
38 |
Correct |
82 ms |
12576 KB |
Output is correct |
39 |
Correct |
86 ms |
12468 KB |
Output is correct |
40 |
Correct |
112 ms |
12428 KB |
Output is correct |
41 |
Correct |
81 ms |
12436 KB |
Output is correct |
42 |
Correct |
79 ms |
11616 KB |
Output is correct |
43 |
Correct |
91 ms |
12588 KB |
Output is correct |
44 |
Correct |
84 ms |
12588 KB |
Output is correct |
45 |
Correct |
72 ms |
12576 KB |
Output is correct |
46 |
Correct |
96 ms |
12728 KB |
Output is correct |
47 |
Execution timed out |
2067 ms |
4152 KB |
Time limit exceeded |
48 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
3 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2672 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2772 KB |
Output is correct |
10 |
Correct |
49 ms |
9808 KB |
Output is correct |
11 |
Correct |
63 ms |
11388 KB |
Output is correct |
12 |
Correct |
72 ms |
11244 KB |
Output is correct |
13 |
Correct |
70 ms |
11788 KB |
Output is correct |
14 |
Correct |
82 ms |
11816 KB |
Output is correct |
15 |
Correct |
68 ms |
10036 KB |
Output is correct |
16 |
Correct |
122 ms |
13196 KB |
Output is correct |
17 |
Correct |
118 ms |
13068 KB |
Output is correct |
18 |
Correct |
132 ms |
13572 KB |
Output is correct |
19 |
Correct |
130 ms |
13580 KB |
Output is correct |
20 |
Correct |
111 ms |
13780 KB |
Output is correct |
21 |
Correct |
108 ms |
14040 KB |
Output is correct |
22 |
Correct |
109 ms |
14108 KB |
Output is correct |
23 |
Correct |
112 ms |
13956 KB |
Output is correct |
24 |
Correct |
117 ms |
14192 KB |
Output is correct |
25 |
Correct |
130 ms |
13716 KB |
Output is correct |
26 |
Correct |
107 ms |
13944 KB |
Output is correct |
27 |
Correct |
126 ms |
13684 KB |
Output is correct |
28 |
Correct |
4 ms |
2772 KB |
Output is correct |
29 |
Correct |
3 ms |
2772 KB |
Output is correct |
30 |
Correct |
4 ms |
2772 KB |
Output is correct |
31 |
Correct |
3 ms |
2772 KB |
Output is correct |
32 |
Correct |
3 ms |
2752 KB |
Output is correct |
33 |
Correct |
2 ms |
2772 KB |
Output is correct |
34 |
Correct |
2 ms |
2772 KB |
Output is correct |
35 |
Correct |
2 ms |
2772 KB |
Output is correct |
36 |
Correct |
2 ms |
2772 KB |
Output is correct |
37 |
Correct |
9 ms |
4104 KB |
Output is correct |
38 |
Correct |
78 ms |
12532 KB |
Output is correct |
39 |
Correct |
82 ms |
12576 KB |
Output is correct |
40 |
Correct |
86 ms |
12468 KB |
Output is correct |
41 |
Correct |
112 ms |
12428 KB |
Output is correct |
42 |
Correct |
81 ms |
12436 KB |
Output is correct |
43 |
Correct |
79 ms |
11616 KB |
Output is correct |
44 |
Correct |
91 ms |
12588 KB |
Output is correct |
45 |
Correct |
84 ms |
12588 KB |
Output is correct |
46 |
Correct |
72 ms |
12576 KB |
Output is correct |
47 |
Correct |
96 ms |
12728 KB |
Output is correct |
48 |
Execution timed out |
2067 ms |
4152 KB |
Time limit exceeded |
49 |
Halted |
0 ms |
0 KB |
- |