#include <bits/stdc++.h>
#include <cstdlib>
#include <stdlib.h>
using namespace std;
/*
#define cin fin
#define cout fout
string __fname = ""; ifstream fin(__fname + ".in"); ofstream fout(__fname + ".out");
*/
#define ull unsigned long long
#define ll long long
#define int long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
ll mod = 1e9 + 7;
const int inf = 1e18;
const int N = 3e5 + 100;
vector<vector<int>> a;
int n, m;
struct dsu{
int sz = 0;
vector<int> p, cnt;
vector<bool> sw;
dsu(int n, int m){
sz = n;
p.resize(n + m + 5);
cnt.resize(n, 0ll);
sw.resize(n + m + 5, 0);
for(int i = 0; i < n + m + 5; i++)
p[i] = i;
}
int find(int u){
return p[u] == u ? u : p[u] = find(p[u]);
}
void merge(int u, int v){
if(u < n && v < n){
cnt[u]++, cnt[v]++;
if(cnt[u] > 2)
sw[sz] = 1;
if(cnt[v] > 2)
sw[sz] = 1;
}
u = find(u);
v = find(v);
if(u == v){
p[sz] = p[u] = sz;
a[sz].push_back(u);
sw[sz] = 1;
sz++;
return;
}
p[sz] = p[u] = p[v] = sz;
a[sz].push_back(u);
a[sz].push_back(v);
if(sw[u] || sw[v])
sw[sz] = 1;
sz++;
}
};
struct edge{
int w, u, v;
};
const int K = 26;
vector<vector<int>> st;
vector<int> euler, h, first, d;
void build(vector<int> & height){
int n = height.size();
st = vector<vector<int>> (K, vector<int> (n+2, 0ll));
for(int i = 0; i<n; i++)
st[0][i] = i;
for(int i = 1; i<K; i++)
for(int j = 0; j + (1 << i) <= n; j++)
if(height[st[i-1][j]] < height[st[i-1][j + (1 << (i - 1))]])
st[i][j] = st[i-1][j];
else
st[i][j] = st[i-1][j + (1 << (i - 1))];
}
int get(vector<int> & height, int l, int r){
int i = 64 - __builtin_clzll(r - l + 1) - 1;
if(height[st[i][l]] < height[st[i][r - (1 << i) + 1]])
return st[i][l];
return st[i][r - (1 << i) + 1];
}
vector<int> first_reachable, is_reachable;
void dfs(int u, int p = -1, int k = 0){
euler.push_back(u);
h[euler.size() - 1] = k;
first[u] = euler.size() - 1;
if(p > -1 && !is_reachable[u])
first_reachable[u] = first_reachable[p];
for(auto i : a[u])
if(i != p){
dfs(i, u, k + 1);
euler.push_back(u);
h[euler.size() - 1] = k;
}
}
int lca(int u, int v){
if(first[u] > first[v])
swap(u, v);
return euler[get(h, first[u], first[v])];
}
vector<edge> edges;
void init(int N, int M, int u[], int v[], int w[]){
n = N;
m = M;
a = vector<vector<int>> (n + m + 5);
for(int i = 0; i<m; i++)
edges.push_back({w[i], u[i], v[i]});
sort(all(edges), [&] (edge a, edge b){
return a.w < b.w;
});
dsu ds(n, m);
for(auto i : edges)
ds.merge(i.u, i.v);
first = vector<int> (2 * (n + m + 5));
h = vector<int> (4 * (n + m + 5));
first_reachable = is_reachable = vector<int> (ds.sw.size(), 0ll);
for(int i = 0; i < first_reachable.size(); i++)
if(ds.sw[i])
is_reachable[i] = 1, first_reachable[i] = i;
dfs(ds.sz - 1);
build(h);
}
int getMinimumFuelCapacity(int u, int v){
int l = lca(u, v);
if(l >= n && is_reachable[l])
return edges[l - n].w;
if(first_reachable[l] >= n && is_reachable[first_reachable[l]])
return edges[first_reachable[l] - n].w;
return -1;
}
Compilation message
swap.cpp: In function 'void init(long long int, long long int, long long int*, long long int*, long long int*)':
swap.cpp:156:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
156 | for(int i = 0; i < first_reachable.size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccnDsqyz.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> >)'
/usr/bin/ld: grader.cpp:(.text.startup+0x217): undefined reference to `getMinimumFuelCapacity(int, int)'
collect2: error: ld returned 1 exit status
