#include <bits/stdc++.h>
#include <chrono>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef vector<int> vi;
struct segTree{
vector<int> t, at;
int maxN, id;
segTree(){
id = rng();
}
void init(int n){
maxN = n, t.resize(2*n, 0);
at.resize(n);
}
void update(int poz, int val){
for(t[poz += maxN] = val; poz > 1; poz>>=1)
t[poz>>1] = min(t[poz], t[poz^1]);
}
int get(int l, int r){
int ans = 0;
for(l += maxN, r += maxN; l < r; l>>=1, r>>=1){
if(l&1) ans = min(ans, t[l++]);
if(r&1) ans = min(ans, t[--r]);
}
return ans;
}
};
typedef pair<int,int> pii;
#define xx first
#define yy second
struct node{
vector<pii> to, tt, father = *new vector<pii>(20, {-1, 1e9});
segTree* tree;
int poz, cnt, depth = 0, g;
bool was = false;
multiset<int> here;
};
vector<node> graph;
int cnt(int v){
graph[v].cnt = 1, graph[v].was = true;
for(pii& a : graph[v].to)
if(!graph[a.xx].was) graph[v].cnt += cnt(a.xx);
graph[v].was = false;
return graph[v].cnt;
}
bool sortFunc(pii a, pii b){
return graph[a.xx].cnt < graph[b.xx].cnt;
}
void build(int v, pii with, int poz, segTree* tree, int g = 0, int s = 1){
graph[v].g = g;
//heavy-light
if(with.xx != -1) graph[v].depth = graph[with.xx].depth;
sort(graph[v].to.begin(), graph[v].to.end(), sortFunc);
if(graph[v].to.size() > s) build(graph[v].to[s].xx, {v, graph[v].to[s].yy}, poz+1, tree);
int mnm = 1e9;
for(int i = s+1; i < graph[v].to.size(); i++)
build(graph[v].to[i].xx, {v, graph[v].to[i].yy}, 0, new segTree()), mnm = min(mnm, graph[v].to[i].yy);
if(graph[v].to.size() == 1) tree->init(poz+1);
tree->update(poz, mnm);
tree->at[graph[v].poz] = v;
for(int i = s; i < graph[v].to.size(); i++)
graph[v].here.insert(graph[v].to[i].yy);
//lca
graph[v].father[0] = with;
int f = with.xx;
for(int i = 1; i < 20 && f != -1; i++){
graph[v].father[i] = {graph[f].father[i-1].xx, max(graph[f].father[i-1].yy, graph[v].father[i-1].yy)};
f = graph[v].father[i].xx;
}
}
pii lca(int a, int b){
if(graph[a].depth < graph[b].depth);
int mxm = 0;
for(int i = 19; i >= 0; i--)
if(graph[graph[a].father[i].xx].depth >= graph[b].depth)
mxm = max(mxm, graph[a].father[i].yy), a = graph[a].father[i].xx;
if(a == b) return {a, mxm};
for(int i = 19; i >= 0; i--){
if(graph[a].father[i].xx != graph[b].father[i].xx || i == 0){
mxm = max(mxm, max(graph[a].father[i].yy, graph[b].father[i].yy));
a = graph[a].father[i].xx, b = graph[b].father[i].xx;
}
}
return {a,mxm};
}
void init(int N, int M, vi U, vi V, vi W){
for(int i = 0; i < M; i++){
graph[U[i]].to.push_back({V[i], W[i]});
graph[V[i]].to.push_back({U[i], W[i]});
}
build(0, {-1, 0}, 0, new segTree(), 0, 0);
}
pii get(int poz, int d){
int mnm = 1e9;
while(graph[poz].depth > d){
if(graph[poz].poz == 0){
int f = graph[poz].father[0].xx, y = graph[poz].father[0].yy;
graph[f].here.erase(graph[f].here.find(y));
if(graph[f].here.size() > 0)
mnm = min(mnm, *graph[f].here.begin());
graph[f].here.insert(y);
poz = f;
}
else{
int to = max(0, graph[poz].poz - (graph[poz].depth - d) );
mnm = min(mnm, graph[poz].tree->get(to, graph[poz].poz));
poz = graph[poz].tree->at[to];
}
}
return {poz, mnm};
}
int at(int f, int a, int b){
int x = graph[a].father[0].yy, y = graph[b].father[0].yy;
graph[f].here.erase(graph[f].here.find(y)), graph[f].here.erase(graph[f].here.find(x));
int ans = 1e9;
if(graph[f].here.size() > 0)
ans = min(ans, *graph[f].here.begin());
graph[f].here.insert(y), graph[f].here.insert(x);
return ans;
}
int getMinimumFuelCapacity(int X, int Y){
pii l = lca(X,Y);
if(graph[X].depth > graph[Y].depth) swap(X,Y);
pii a = get(Y, graph[l.xx].depth+1);
if(X == l.xx)
return max(l.yy, a.yy);
pii b = get(X, graph[l.xx].depth+1);
int mnm = min(a.yy, b.yy);
mnm = min(mnm, at(l.xx, a.xx, b.xx));
return max(mnm, l.yy);
}
Compilation message
swap.cpp: In function 'void build(int, pii, int, segTree*, int, int)':
swap.cpp:55:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
55 | if(graph[v].to.size() > s) build(graph[v].to[s].xx, {v, graph[v].to[s].yy}, poz+1, tree);
| ~~~~~~~~~~~~~~~~~~~^~~
swap.cpp:57:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int i = s+1; i < graph[v].to.size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~~
swap.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i = s; i < graph[v].to.size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
384 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
384 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
384 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
384 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
384 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
384 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
