#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define ll long long
#define pri pair<int,int>
#define prl pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pair<int,int>>
#define vpl vector<pair<ll,ll>>
#define re return 0
#define sqrt sqrtl
vi dsu;
vi parent;
vi cnt;
vi sz;
vi weight;
vector<vi> adj;
void make_set(int x) {
dsu[x] = x;
parent[x] = x;
sz[x] = 1;
cnt[x] = 0;
weight[x] = 0;
}
int get_root(int u) {
if (dsu[u]==u) return u;
return dsu[u] = get_root(dsu[u]);
}
int s;
vp edges;
void unite(int u,int v,int w) {
edges[s] = {u,v};
u = get_root(u);
v = get_root(v);
//cout<<"uniting "<<u<<" and "<<v<<" to "<<s<<endl;
make_set(s);
dsu[u] = dsu[v] = s;
parent[u] = parent[v] = s;
adj[s].push_back(u);
weight[s] = w;
if (u==v) sz[s]+=sz[u], cnt[s]+=cnt[u];
else {
sz[s]+=sz[u]+sz[v];
cnt[s]+=cnt[u]+cnt[v];
adj[s].push_back(v);
}
s++;
}
void tour(int u) {
cout<<u<<" "<<weight[u]<<endl;
for (auto m : adj[u]) {
//cout<<"niggas gonna from "<<u<<" to "<<m<<endl;
tour(m);
}
}
vector<vi> adj_mst;
vi stf;
vp chain;
void dfs(int u) {
if (chain[u].first==-1) stf[u] = u;
else if (parent[u]!=u) stf[u] = stf[parent[u]];
else stf[u] = -1;
for (auto m : adj[u]) {
dfs(m);
}
}
pri cc(pri a,pri b,pri c) {
//chain,chain,edge
if (a.first == c.first && b.first == c.second) {
return {a.second,b.second};
}
if (a.second == c.first && b.first == c.second) {
return {a.first,b.second};
}
if (a.first == c.first && b.second == c.second) {
return {a.second,b.first};
}
if (a.second == c.first && b.second == c.second) {
return {a.first,b.first};
}
return {-1,-1};
}
vp ln2;
vp lnf;
vp seg2;
void dfs2(int u,int h) { // on the reachability tree
lnf[u].first = ln2.size();
ln2.push_back({h,u});
for (auto v : adj[u]) {
dfs2(v,h+1);
ln2.push_back({h,u});
}
if (adj[u].size()==0) chain[u] = {u,u};
else if (adj[u].size()==1) chain[u] = {-1,-1};
else if (chain[adj[u][0]].first==-1 || chain[adj[u][1]].first==-1) chain[u]={-1,-1};
else {
//each child forms a chain
//edge is edges[u].first - edges[u].second
auto uc = chain[adj[u][0]];
auto vc = chain[adj[u][1]];
chain[u] = cc(uc,vc,edges[u]);
}
lnf[u].second = ln2.size()-1;
}
int lca2(int u,int v) {
int l = min(lnf[u].first,lnf[v].first);
int r = max(lnf[u].second,lnf[v].second);
l+=ln2.size();
r+=ln2.size();
r++;
pri ans = {1e9,1e9};
for (;l<r;l>>=1,r>>=1) {
if (l&1) {
ans = min(ans,seg2[l++]);
} if (r&1) {
ans = min(ans,seg2[--r]);
}
}
return ans.second;
}
int getMinimumFuelCapacity(int u,int v) {
//pri lca1_ = lca(u,v);
int lca2_ = lca2(u,v);
//int path_len = node_l[fl[u].first].first+node_l[fl[v].first].first - lca1_.second*2;
if (chain[lca2_].first==-1) {
return weight[lca2_];
} else {
//find earliest parent with no chain
if (stf[lca2_]==-1) return -1;
else return weight[stf[lca2_]];
}
}
void init(int n,int m,int u[],int v[],int w[]) {
dsu = vi(2*n+1);
parent = vi(2*n+1);
sz = vi(2*n+1);
cnt = vi(2*n+1);
adj = vector<vi>(2*n+1);
weight = vi(2*n+1);
s = n;
struct edge {
int u,v,w;
bool operator<(const edge& other) const {
return w<other.w;
}
};
for (int i = 0;i<n;i++){
make_set(i);
cnt[i] = 1;
}
//cout<<"nigga"<<endl;
vector<edge> ss;
vector<edge> edging;
for (int i = 0;i<m;i++) ss.push_back(edge{u[i],v[i],w[i]});
sort(ss.begin(),ss.end());
adj_mst = vector<vi>(n);
edges = vp(2*n+1);
for (auto edge : ss) {
if (get_root(edge.u)!=get_root(edge.v)) {
adj_mst[edge.u].push_back(edge.v);
adj_mst[edge.v].push_back(edge.u);
}
unite(edge.u,edge.v,edge.w);
}
//cout<<cnt[s-1]<<endl;
lnf = vp(2*n+1);
chain = vp(2*n+1);
dfs2(s-1,0);
seg2 = vp(2*ln2.size()+2);
for (int i = 0;i<ln2.size();i++) {
seg2[i+ln2.size()] = ln2[i];
}
for (int i = ln2.size()-1;i>0;i--) {
seg2[i] = min(seg2[2*i],seg2[2*i+1]);
}
stf = vi(2*n+1);
dfs(s-1);
}
/*int32_t main() {
int u[6] = {0,0,1,1,1,2};
int v[6] = {1,2,2,3,4,3};
int w[6] = {4,4,1,2,10,3};
init(5, 6, u, v,w);
cout<<getMinimumFuelCapacity(1,2)<<endl;
return 0;
}*/
Compilation message
swap.cpp: In function 'void init(int, int, int*, int*, int*)':
swap.cpp:195:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
195 | for (int i = 0;i<ln2.size();i++) {
| ~^~~~~~~~~~~
/usr/bin/ld: /tmp/ccopWXlR.o: in function `main':
grader.cpp:(.text.startup+0x1c3): undefined reference to `init(int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
