#include "swap.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
struct Edge{
int s, e, x;
bool operator < (const Edge &t) const {
return tie(x, s, e) < tie(t.x, t.s, t.e);
}
};
int par[101010];
int find(int v){ return v == par[v] ? v : par[v] = find(par[v]); }
int merge(int u, int v){
u = find(u); v = find(v);
if(u == v) return 0;
par[u] = v; return 1;
}
const int sz = 1 << 17;
struct Seg{
int tree[1 << 18];
void update(int x, int v){
x |= sz; tree[x] = v;
while(x >>= 1) tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
}
int query(int l, int r){
l |= sz; r |= sz; int ret = 0;
while(l <= r){
if(l & 1) ret = max(ret, tree[l++]);
if(~r & 1) ret = max(ret, tree[r--]);
l >>= 1; r >>= 1;
}
return ret;
}
};
struct HLD{
vector<p> inp[101010];
vector<int> g[101010];
int w[101010], pv;
int in[101010], top[101010], dep[101010], sz[101010], par[101010];
Seg seg;
void dfs(int v, int b){
for(auto i : inp[v]) if(i.x != b) {
g[v].push_back(i.x); w[i.x] = i.y;
dep[i.x] = dep[v] + 1; par[i.x] = v;
dfs(i.x, v);
}
}
void dfs1(int v){
sz[v] = 1;
for(auto &i : g[v]){
dfs1(i); sz[v] += sz[i];
if(sz[i] > sz[g[v][0]]) swap(i, g[v][0]);
}
}
void dfs2(int v){
in[v] = ++pv;
for(auto i : g[v]){
top[i] = i == g[v][0] ? top[v] : i;
dfs2(i);
}
}
void init(int n){
dfs(0, -1); dfs1(0); dfs2(0);
for(int i=0; i<n; i++) seg.update(in[i], w[i]);
}
int query(int u, int v){
int ret = 0;
for(; top[u] != top[v]; u=par[top[u]]){
if(dep[top[u]] < dep[top[v]]) swap(u, v);
ret = max(ret, seg.query(in[top[u]], in[u]));
}
if(dep[u] > dep[v]) swap(u, v);
ret = max(ret, seg.query(in[u]+1, in[v]));
return ret;
}
void addEdge(int s, int e, int x){
inp[s].emplace_back(e, x);
inp[e].emplace_back(s, x);
}
} t1, t2;
int n, m, deg[101010], flag;
vector<Edge> edge;
vector<int> g[101010];
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N; m = M; edge.resize(m);
for(int i=0; i<m; i++){
edge[i].s = U[i]; edge[i].e = V[i]; edge[i].x = W[i];
g[edge[i].s].push_back(edge[i].e);
g[edge[i].e].push_back(edge[i].s);
}
sort(all(edge)); iota(par, par+101010, 0);
for(auto i : edge){
if(merge(i.s, i.e)) t1.addEdge(i.s, i.e, i.x), t2.addEdge(i.s, i.e, i.x);
else{
if(merge(i.s, n)) t2.addEdge(i.s, n, i.x);
if(merge(i.e, n)) t2.addEdge(i.e, n, i.x);
}
if(++deg[i.s] == 3 && merge(i.s, n)) t2.addEdge(i.s, n, i.x);
if(++deg[i.e] == 3 && merge(i.e, n)) t2.addEdge(i.e, n, i.x);
}
for(int i=0; i<n; i++) if(deg[i] >= 3) flag = 1;
if(n <= m) flag = 1;
t1.init(n); t2.init(n+1);
}
int getMinimumFuelCapacity(int a, int b){
if(!flag) return -1;
return max({t1.query(a, b), t2.query(a, n), t2.query(b, n)});
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
12672 KB |
Output is correct |
2 |
Correct |
9 ms |
12672 KB |
Output is correct |
3 |
Correct |
9 ms |
12672 KB |
Output is correct |
4 |
Correct |
9 ms |
12800 KB |
Output is correct |
5 |
Correct |
10 ms |
13056 KB |
Output is correct |
6 |
Correct |
10 ms |
13056 KB |
Output is correct |
7 |
Correct |
11 ms |
13056 KB |
Output is correct |
8 |
Correct |
10 ms |
13056 KB |
Output is correct |
9 |
Correct |
208 ms |
40952 KB |
Output is correct |
10 |
Correct |
269 ms |
49016 KB |
Output is correct |
11 |
Correct |
261 ms |
47864 KB |
Output is correct |
12 |
Correct |
279 ms |
50296 KB |
Output is correct |
13 |
Correct |
249 ms |
52472 KB |
Output is correct |
14 |
Correct |
213 ms |
40056 KB |
Output is correct |
15 |
Correct |
360 ms |
50692 KB |
Output is correct |
16 |
Correct |
329 ms |
47532 KB |
Output is correct |
17 |
Correct |
373 ms |
54496 KB |
Output is correct |
18 |
Correct |
293 ms |
52192 KB |
Output is correct |
19 |
Correct |
148 ms |
22520 KB |
Output is correct |
20 |
Correct |
439 ms |
51064 KB |
Output is correct |
21 |
Correct |
433 ms |
48692 KB |
Output is correct |
22 |
Correct |
460 ms |
52864 KB |
Output is correct |
23 |
Correct |
406 ms |
53220 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
12672 KB |
Output is correct |
2 |
Correct |
9 ms |
12672 KB |
Output is correct |
3 |
Correct |
230 ms |
38896 KB |
Output is correct |
4 |
Correct |
235 ms |
40008 KB |
Output is correct |
5 |
Correct |
237 ms |
39672 KB |
Output is correct |
6 |
Correct |
239 ms |
39756 KB |
Output is correct |
7 |
Correct |
242 ms |
39732 KB |
Output is correct |
8 |
Correct |
228 ms |
38672 KB |
Output is correct |
9 |
Correct |
229 ms |
39520 KB |
Output is correct |
10 |
Correct |
225 ms |
38556 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
12672 KB |
Output is correct |
2 |
Correct |
9 ms |
12672 KB |
Output is correct |
3 |
Correct |
9 ms |
12672 KB |
Output is correct |
4 |
Correct |
9 ms |
12672 KB |
Output is correct |
5 |
Correct |
9 ms |
12800 KB |
Output is correct |
6 |
Correct |
10 ms |
13056 KB |
Output is correct |
7 |
Correct |
10 ms |
13056 KB |
Output is correct |
8 |
Correct |
11 ms |
13056 KB |
Output is correct |
9 |
Correct |
10 ms |
13056 KB |
Output is correct |
10 |
Incorrect |
10 ms |
12928 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
12672 KB |
Output is correct |
2 |
Correct |
9 ms |
12672 KB |
Output is correct |
3 |
Correct |
9 ms |
12672 KB |
Output is correct |
4 |
Correct |
9 ms |
12672 KB |
Output is correct |
5 |
Correct |
9 ms |
12800 KB |
Output is correct |
6 |
Correct |
10 ms |
13056 KB |
Output is correct |
7 |
Correct |
10 ms |
13056 KB |
Output is correct |
8 |
Correct |
11 ms |
13056 KB |
Output is correct |
9 |
Correct |
10 ms |
13056 KB |
Output is correct |
10 |
Correct |
208 ms |
40952 KB |
Output is correct |
11 |
Correct |
269 ms |
49016 KB |
Output is correct |
12 |
Correct |
261 ms |
47864 KB |
Output is correct |
13 |
Correct |
279 ms |
50296 KB |
Output is correct |
14 |
Correct |
249 ms |
52472 KB |
Output is correct |
15 |
Incorrect |
10 ms |
12928 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
12672 KB |
Output is correct |
2 |
Correct |
9 ms |
12672 KB |
Output is correct |
3 |
Correct |
9 ms |
12672 KB |
Output is correct |
4 |
Correct |
9 ms |
12800 KB |
Output is correct |
5 |
Correct |
10 ms |
13056 KB |
Output is correct |
6 |
Correct |
10 ms |
13056 KB |
Output is correct |
7 |
Correct |
11 ms |
13056 KB |
Output is correct |
8 |
Correct |
10 ms |
13056 KB |
Output is correct |
9 |
Correct |
208 ms |
40952 KB |
Output is correct |
10 |
Correct |
269 ms |
49016 KB |
Output is correct |
11 |
Correct |
261 ms |
47864 KB |
Output is correct |
12 |
Correct |
279 ms |
50296 KB |
Output is correct |
13 |
Correct |
249 ms |
52472 KB |
Output is correct |
14 |
Correct |
213 ms |
40056 KB |
Output is correct |
15 |
Correct |
360 ms |
50692 KB |
Output is correct |
16 |
Correct |
329 ms |
47532 KB |
Output is correct |
17 |
Correct |
373 ms |
54496 KB |
Output is correct |
18 |
Correct |
293 ms |
52192 KB |
Output is correct |
19 |
Correct |
230 ms |
38896 KB |
Output is correct |
20 |
Correct |
235 ms |
40008 KB |
Output is correct |
21 |
Correct |
237 ms |
39672 KB |
Output is correct |
22 |
Correct |
239 ms |
39756 KB |
Output is correct |
23 |
Correct |
242 ms |
39732 KB |
Output is correct |
24 |
Correct |
228 ms |
38672 KB |
Output is correct |
25 |
Correct |
229 ms |
39520 KB |
Output is correct |
26 |
Correct |
225 ms |
38556 KB |
Output is correct |
27 |
Incorrect |
10 ms |
12928 KB |
Output isn't correct |
28 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
12672 KB |
Output is correct |
2 |
Correct |
9 ms |
12672 KB |
Output is correct |
3 |
Correct |
9 ms |
12672 KB |
Output is correct |
4 |
Correct |
9 ms |
12672 KB |
Output is correct |
5 |
Correct |
9 ms |
12800 KB |
Output is correct |
6 |
Correct |
10 ms |
13056 KB |
Output is correct |
7 |
Correct |
10 ms |
13056 KB |
Output is correct |
8 |
Correct |
11 ms |
13056 KB |
Output is correct |
9 |
Correct |
10 ms |
13056 KB |
Output is correct |
10 |
Correct |
208 ms |
40952 KB |
Output is correct |
11 |
Correct |
269 ms |
49016 KB |
Output is correct |
12 |
Correct |
261 ms |
47864 KB |
Output is correct |
13 |
Correct |
279 ms |
50296 KB |
Output is correct |
14 |
Correct |
249 ms |
52472 KB |
Output is correct |
15 |
Correct |
213 ms |
40056 KB |
Output is correct |
16 |
Correct |
360 ms |
50692 KB |
Output is correct |
17 |
Correct |
329 ms |
47532 KB |
Output is correct |
18 |
Correct |
373 ms |
54496 KB |
Output is correct |
19 |
Correct |
293 ms |
52192 KB |
Output is correct |
20 |
Correct |
230 ms |
38896 KB |
Output is correct |
21 |
Correct |
235 ms |
40008 KB |
Output is correct |
22 |
Correct |
237 ms |
39672 KB |
Output is correct |
23 |
Correct |
239 ms |
39756 KB |
Output is correct |
24 |
Correct |
242 ms |
39732 KB |
Output is correct |
25 |
Correct |
228 ms |
38672 KB |
Output is correct |
26 |
Correct |
229 ms |
39520 KB |
Output is correct |
27 |
Correct |
225 ms |
38556 KB |
Output is correct |
28 |
Incorrect |
10 ms |
12928 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |