#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
return l + rd() % (r - l + 1);
}
const int N = 2e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);
vector <int> adj[N];
int max_e[N][20];
int ok_e[N][20];
int ok_v[N][20];
int anc[N][20];
int par[N];
int deg[N];
int fr[N];
int to[N];
int w[N];
int h[N];
int n,m;
bool notmst[N];
int getpar(int u) {
return (par[u] < 0) ? u : (par[u] = getpar(par[u]));
}
bool join(int u, int v) {
u = getpar(u);
v = getpar(v);
if (u == v)
return false;
if (par[u] > par[v])
swap(u, v);
par[u] += par[v];
par[v] = u;
return true;
}
int getlca(int u, int v) {
if (h[u] > h[v])
swap(u, v);
for (int i = 19; i >= 0; i--)
if (h[v] - bit(i) >= h[u])
v = anc[v][i];
if (u == v)
return v;
for (int i = 19; i >= 0; i--) if (anc[u][i] != anc[v][i]) {
u = anc[u][i];
v = anc[v][i];
}
return anc[v][0];
}
void dfs(int u, int p = -1) {
anc[u][0] = p;
for (int i : adj[u]) {
int v = fr[i] ^ to[i] ^ u;
if (v == p)
continue;
h[v] = h[u] + 1;
max_e[v][0] = w[i];
dfs(v, u);
}
}
void build() {
vector <int> ind(m, 0);
iota(ALL(ind), 0);
sort(ALL(ind), [](int i, int j) {
return w[i] < w[j];
});
for (int i = 0; i < n; i++)
par[i] = -1;
for (int i : ind) {
if (join(fr[i], to[i])) {
adj[fr[i]].push_back(i);
adj[to[i]].push_back(i);
} else
notmst[i] = true;
}
dfs(0);
for (int j = 1; j < 20; j++)
for (int i = 0; i < n; i++) {
int p = anc[i][j - 1];
anc[i][j] = (p < 0) ? -1 : (anc[p][j - 1]);
}
for (int i = 0; i < n; i++) {
par[i] = -1;
ok_v[i][0] = ok_e[i][0] = 2 * oo;
}
max_e[0][0] = 2 * oo;
for (int it : ind) if (notmst[it]) {
int u = fr[it];
int v = to[it];
int p = getlca(u, v);
for (int i = getpar(u); h[i] > h[p]; i = getpar(i)) {
ok_e[i][0] = w[it];
par[i] = anc[i][0];
}
for (int i = getpar(v); h[i] > h[p]; i = getpar(i)) {
ok_e[i][0] = w[it];
par[i] = anc[i][0];
}
}
for (int it : ind) {
int u = fr[it];
int v = to[it];
deg[u]++;
deg[v]++;
if (deg[u] == 3)
ok_v[u][0] = w[it];
if (deg[v] == 3)
ok_v[v][0] = w[it];
}
for (int j = 1; j < 20; j++)
for (int i = 0; i < n; i++) {
int p = anc[i][j - 1];
if (p < 0) {
max_e[i][j] = ok_v[i][j] = ok_e[i][j] = 2 * oo;
} else {
ok_v[i][j] = min(ok_v[i][j - 1], ok_v[p][j - 1]);
ok_e[i][j] = min(ok_e[i][j - 1], ok_e[p][j - 1]);
max_e[i][j] = max(max_e[i][j - 1], max_e[p][j - 1]);
}
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N;
m = M;
for (int i = 0; i < m; i++) {
fr[i] = U[i];
to[i] = V[i];
w[i] = W[i];
}
build();
}
int getmax(int u, int p) {
int res = 0;
for (int i = 19; i >= 0; i--) if (h[u] - bit(i) >= h[p]) {
maxi(res, max_e[u][i]);
u = anc[u][i];
}
return res;
}
int minEdge(int u, int p) {
int res = 2 * oo;
for (int i = 19; i >= 0; i--) if (h[u] - bit(i) >= h[p]) {
mini(res, ok_e[u][i]);
u = anc[u][i];
}
return res;
}
int minVertex(int u, int p) {
int res = 2 * oo;
u = anc[u][0];
for (int i = 19; i >= 0; i--) if (h[u] - bit(i) > h[p]) {
mini(res, ok_v[u][i]);
u = anc[u][i];
}
return res;
}
int getMinimumFuelCapacity(int u, int v) {
if (h[u] > h[v])
swap(u, v);
int p = getlca(u, v);
int res = max(getmax(u, p), getmax(v, p));
int ed = min(minEdge(u, p), minEdge(v, p));
int vt = min(minVertex(u, p), minVertex(v, p));
if (v != p)
mini(vt, ok_v[p][0]);
// cerr << u << " " << v << " " << vt << " " << ed << "\n";
maxi(res, min(vt, ed));
if (res == 2 * oo)
res = -1;
return res;
}
#include "swap.h"
//#include "grader.cpp"
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4960 KB |
Output is correct |
2 |
Correct |
3 ms |
5076 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
3 ms |
5148 KB |
Output is correct |
5 |
Correct |
4 ms |
5408 KB |
Output is correct |
6 |
Correct |
4 ms |
5460 KB |
Output is correct |
7 |
Correct |
4 ms |
5460 KB |
Output is correct |
8 |
Correct |
4 ms |
5460 KB |
Output is correct |
9 |
Correct |
144 ms |
41420 KB |
Output is correct |
10 |
Correct |
183 ms |
50920 KB |
Output is correct |
11 |
Correct |
202 ms |
49688 KB |
Output is correct |
12 |
Correct |
183 ms |
52628 KB |
Output is correct |
13 |
Correct |
178 ms |
54480 KB |
Output is correct |
14 |
Correct |
187 ms |
40980 KB |
Output is correct |
15 |
Correct |
668 ms |
54732 KB |
Output is correct |
16 |
Correct |
719 ms |
51992 KB |
Output is correct |
17 |
Correct |
687 ms |
58140 KB |
Output is correct |
18 |
Correct |
740 ms |
56848 KB |
Output is correct |
19 |
Correct |
195 ms |
17868 KB |
Output is correct |
20 |
Correct |
683 ms |
55120 KB |
Output is correct |
21 |
Correct |
722 ms |
52892 KB |
Output is correct |
22 |
Correct |
717 ms |
57228 KB |
Output is correct |
23 |
Correct |
724 ms |
57576 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4960 KB |
Output is correct |
2 |
Correct |
3 ms |
5076 KB |
Output is correct |
3 |
Correct |
324 ms |
49216 KB |
Output is correct |
4 |
Correct |
310 ms |
51312 KB |
Output is correct |
5 |
Correct |
301 ms |
50276 KB |
Output is correct |
6 |
Correct |
315 ms |
51052 KB |
Output is correct |
7 |
Correct |
316 ms |
50732 KB |
Output is correct |
8 |
Correct |
322 ms |
49044 KB |
Output is correct |
9 |
Correct |
302 ms |
50300 KB |
Output is correct |
10 |
Correct |
306 ms |
48628 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4960 KB |
Output is correct |
2 |
Correct |
3 ms |
5076 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
3 ms |
5148 KB |
Output is correct |
5 |
Correct |
4 ms |
5408 KB |
Output is correct |
6 |
Correct |
4 ms |
5460 KB |
Output is correct |
7 |
Correct |
4 ms |
5460 KB |
Output is correct |
8 |
Correct |
4 ms |
5460 KB |
Output is correct |
9 |
Correct |
4 ms |
5076 KB |
Output is correct |
10 |
Correct |
4 ms |
5428 KB |
Output is correct |
11 |
Correct |
4 ms |
5408 KB |
Output is correct |
12 |
Correct |
4 ms |
5460 KB |
Output is correct |
13 |
Correct |
4 ms |
5332 KB |
Output is correct |
14 |
Correct |
4 ms |
5332 KB |
Output is correct |
15 |
Incorrect |
4 ms |
5460 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5076 KB |
Output is correct |
2 |
Correct |
3 ms |
4960 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
3 ms |
5076 KB |
Output is correct |
5 |
Correct |
3 ms |
5148 KB |
Output is correct |
6 |
Correct |
4 ms |
5408 KB |
Output is correct |
7 |
Correct |
4 ms |
5460 KB |
Output is correct |
8 |
Correct |
4 ms |
5460 KB |
Output is correct |
9 |
Correct |
4 ms |
5460 KB |
Output is correct |
10 |
Correct |
144 ms |
41420 KB |
Output is correct |
11 |
Correct |
183 ms |
50920 KB |
Output is correct |
12 |
Correct |
202 ms |
49688 KB |
Output is correct |
13 |
Correct |
183 ms |
52628 KB |
Output is correct |
14 |
Correct |
178 ms |
54480 KB |
Output is correct |
15 |
Correct |
4 ms |
5428 KB |
Output is correct |
16 |
Correct |
4 ms |
5408 KB |
Output is correct |
17 |
Correct |
4 ms |
5460 KB |
Output is correct |
18 |
Correct |
4 ms |
5332 KB |
Output is correct |
19 |
Correct |
4 ms |
5332 KB |
Output is correct |
20 |
Incorrect |
4 ms |
5460 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4960 KB |
Output is correct |
2 |
Correct |
3 ms |
5076 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
3 ms |
5148 KB |
Output is correct |
5 |
Correct |
4 ms |
5408 KB |
Output is correct |
6 |
Correct |
4 ms |
5460 KB |
Output is correct |
7 |
Correct |
4 ms |
5460 KB |
Output is correct |
8 |
Correct |
4 ms |
5460 KB |
Output is correct |
9 |
Correct |
144 ms |
41420 KB |
Output is correct |
10 |
Correct |
183 ms |
50920 KB |
Output is correct |
11 |
Correct |
202 ms |
49688 KB |
Output is correct |
12 |
Correct |
183 ms |
52628 KB |
Output is correct |
13 |
Correct |
178 ms |
54480 KB |
Output is correct |
14 |
Correct |
187 ms |
40980 KB |
Output is correct |
15 |
Correct |
668 ms |
54732 KB |
Output is correct |
16 |
Correct |
719 ms |
51992 KB |
Output is correct |
17 |
Correct |
687 ms |
58140 KB |
Output is correct |
18 |
Correct |
740 ms |
56848 KB |
Output is correct |
19 |
Correct |
324 ms |
49216 KB |
Output is correct |
20 |
Correct |
310 ms |
51312 KB |
Output is correct |
21 |
Correct |
301 ms |
50276 KB |
Output is correct |
22 |
Correct |
315 ms |
51052 KB |
Output is correct |
23 |
Correct |
316 ms |
50732 KB |
Output is correct |
24 |
Correct |
322 ms |
49044 KB |
Output is correct |
25 |
Correct |
302 ms |
50300 KB |
Output is correct |
26 |
Correct |
306 ms |
48628 KB |
Output is correct |
27 |
Correct |
4 ms |
5428 KB |
Output is correct |
28 |
Correct |
4 ms |
5408 KB |
Output is correct |
29 |
Correct |
4 ms |
5460 KB |
Output is correct |
30 |
Correct |
4 ms |
5332 KB |
Output is correct |
31 |
Correct |
4 ms |
5332 KB |
Output is correct |
32 |
Incorrect |
4 ms |
5460 KB |
Output isn't correct |
33 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5076 KB |
Output is correct |
2 |
Correct |
3 ms |
4960 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
3 ms |
5076 KB |
Output is correct |
5 |
Correct |
3 ms |
5148 KB |
Output is correct |
6 |
Correct |
4 ms |
5408 KB |
Output is correct |
7 |
Correct |
4 ms |
5460 KB |
Output is correct |
8 |
Correct |
4 ms |
5460 KB |
Output is correct |
9 |
Correct |
4 ms |
5460 KB |
Output is correct |
10 |
Correct |
144 ms |
41420 KB |
Output is correct |
11 |
Correct |
183 ms |
50920 KB |
Output is correct |
12 |
Correct |
202 ms |
49688 KB |
Output is correct |
13 |
Correct |
183 ms |
52628 KB |
Output is correct |
14 |
Correct |
178 ms |
54480 KB |
Output is correct |
15 |
Correct |
187 ms |
40980 KB |
Output is correct |
16 |
Correct |
668 ms |
54732 KB |
Output is correct |
17 |
Correct |
719 ms |
51992 KB |
Output is correct |
18 |
Correct |
687 ms |
58140 KB |
Output is correct |
19 |
Correct |
740 ms |
56848 KB |
Output is correct |
20 |
Correct |
324 ms |
49216 KB |
Output is correct |
21 |
Correct |
310 ms |
51312 KB |
Output is correct |
22 |
Correct |
301 ms |
50276 KB |
Output is correct |
23 |
Correct |
315 ms |
51052 KB |
Output is correct |
24 |
Correct |
316 ms |
50732 KB |
Output is correct |
25 |
Correct |
322 ms |
49044 KB |
Output is correct |
26 |
Correct |
302 ms |
50300 KB |
Output is correct |
27 |
Correct |
306 ms |
48628 KB |
Output is correct |
28 |
Correct |
4 ms |
5428 KB |
Output is correct |
29 |
Correct |
4 ms |
5408 KB |
Output is correct |
30 |
Correct |
4 ms |
5460 KB |
Output is correct |
31 |
Correct |
4 ms |
5332 KB |
Output is correct |
32 |
Correct |
4 ms |
5332 KB |
Output is correct |
33 |
Incorrect |
4 ms |
5460 KB |
Output isn't correct |
34 |
Halted |
0 ms |
0 KB |
- |