#include "swap.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 1.5e9;
struct segtree{
int k;
vector<pair<int, int>> mn;
segtree(int n){
k = 1;
while(k <= n) k*=2; k*=2;
mn.assign(k, {inf,0});
for(int i = 0; i < k/2; i++) mn[i+k/2].sc = i;
for(int i = k/2; i > 0; i--) mn[i].sc = mn[2*i].sc;
}
void upd(int in, pair<int, int> x){
in+=k/2;
mn[in] = x, in/=2;
while(in > 0){
mn[in] = min(mn[2*in], mn[2*in+1]);
in/=2;
}
}
pair<int, int> smn(int l, int r, int nd, int a, int b){
if(b < l || a > r) return {inf, inf};
if(a >= l && b <= r) return mn[nd];
int c = (a+b)/2;
return min(smn(l, r, 2*nd, a, c), smn(l, r, 2*nd+1, c+1, b));
}
pair<int, int> smn(int l, int r){
return smn(l, r, 1, 0, k/2-1);
}
}seg(10);
struct reachability_tree{
int n;
vector<int> p;
vector<int> adj;
vector<bool> ok;
vector<vector<int>> v;
vector<int> w;
vector<int> id;
reachability_tree(int n){
reachability_tree::n = n;
v.resize(n);
p.resize(n);
ok.resize(n, 0);
adj.resize(n, 0);
w.resize(n);
for(int i = 0; i < n; i++) p[i] = i;
}
int get(int x){
if(p[x] == x) return p[x] = get(p[x]);
return p[x];
}
void unite(int a, int b, int vl){
int aa = a, bb = b;
a = get(a), b = get(b);
adj[aa]++;
adj[bb]++;
p.pb(n);
ok.pb(0);
v.pb({});
p[a] = n;
p[b] = n;
v[n].pb(a);
if(a != b) v[n].pb(b);
ok[n] = ok[a]|ok[b];
if(max(adj[aa], adj[bb]) >= 3 || a == b) ok[n] = 1;
n++;
w.pb(vl);
}
}rt(0);
int n, m;
vector<int> depth, ett, pos, anc;
void dfs(int nd, int d, int ls){
depth[nd] = d;
ett.pb(nd);
if(rt.ok[nd]) ls = nd;
anc[nd] = ls;
for(int x: rt.v[nd]){
dfs(x, d+1, ls);
ett.pb(nd);
}
}
void init(int n, int m, vector<int> u, vector<int>v, vector<int>w){
::n = n, ::m = m;
rt = reachability_tree(n);
vector<tuple<int, int, int>> edges;
for(int i = 0; i < m; i++){
edges.pb({w[i], u[i], v[i]});
}
sort(edges.begin(), edges.end());
for(auto [wi, ui, vi]: edges) rt.unite(ui, vi, wi);
depth.resize(rt.n);
pos.resize(rt.n);
anc.resize(rt.n);
dfs(rt.get(0), 1, -1);
seg = segtree(ett.size());
for(int i = 0; i < ett.size(); i++) seg.upd(i, {depth[ett[i]], ett[i]});
for(int i = 0; i < rt.n; i++) pos[ett[i]] = i;
}
int getMinimumFuelCapacity(int x, int y){
x = pos[x], y = pos[y];
if(x > y) swap(x, y);
int lca = seg.smn(x, y).sc;
int ans = anc[lca];
if(ans != -1) ans = rt.w[ans];
return ans;
}
Compilation message
swap.cpp: In constructor 'segtree::segtree(int)':
swap.cpp:18:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
18 | while(k <= n) k*=2; k*=2;
| ^~~~~
swap.cpp:18:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
18 | while(k <= n) k*=2; k*=2;
| ^
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:111:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int i = 0; i < ett.size(); i++) seg.upd(i, {depth[ett[i]], ett[i]});
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
336 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
336 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
336 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
336 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
336 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
336 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
