//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define nl cout << "\n"
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
class Dsu{
public:
vector<int> p;
init(int n){
p.resize(n);
iota(all(p), 0);
}
int find(int x){
if(x == p[x]) return x;
return (p[x] = find(p[x]));
}
bool unite(int a, int b){
a = find(a), b = find(b);
if(a == b) return false;
p[b] = a;
return true;
}
};
class MergeSortTree{
public:
vector<vector<int>> st;
MergeSortTree(int N, vector<int>& y){
st.resize(4 * N);
build(0, 0, N - 1, y);
}
void merge(int i){
int cl = 2 * i + 1, cr = 2 * i + 2;
for(int x : st[cl]) st[i].pb(x);
for(int x : st[cr]) st[i].pb(x);
sort(all(st[i]));
}
void build(int i, int l, int r, vector<int>& y){
if(l == r){
if(y[l] != -1)
st[i].pb(y[l]);
} else{
int m = (l + r) / 2;
build(2 * i + 1, l, m, y);
build(2 * i + 2, m + 1, r, y);
merge(i);
}
}
int query(int i, int l, int r, int qlx, int qrx, int qly, int qry){
if(qlx <= l && r <= qrx){
int p = lower_bound(all(st[i]), qly) - st[i].begin();
if(p < SZ(st[i]) && qly <= st[i][p] && st[i][p] <= qry){
return 1;
}
return 0;
}
if(qrx < l || qlx > r)
return 0;
int m = (l + r) / 2;
int ans1 = query(2 * i + 1, l, m, qlx, qrx, qly, qry);
int ans2 = query(2 * i + 2, m + 1, r, qlx, qrx, qly, qry);
return max(ans1, ans2);
}
};
const int MAXN = 1e6;
int N, M, Q;
vector<int> g[MAXN];
int timer, tin[MAXN], tou[MAXN];
void dfs(int v, int p){
tin[v] = timer++;
for(int u : g[v]){
if(u ^ p){
dfs(u, v);
}
}
tou[v] = timer - 1;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
::N = N; M = SZ(X), Q = SZ(S);
int root; Dsu dsu;
auto add_edge = [&](int u, int v){
u = dsu.find(u), v = dsu.find(v);
dsu.unite(root, u);
g[root].pb(u);
if(dsu.unite(root, v)){
g[root].pb(v);
}
root++;
};
vector<int> edge[N];
rep(i, 0, M){
edge[X[i]].pb(Y[i]);
edge[Y[i]].pb(X[i]);
}
vector<int> q[N];
dsu.init(N + M); root = N;
rep(i, 0, Q){
q[L[i]].pb(i);
}
vector<int> a(Q);
per(l, N - 1, 0){
for(int u : edge[l]){
if(u >= l)
add_edge(l, u);
}
for(int i : q[l]){
a[i] = dsu.find(S[i]);
}
q[l].clear();
}
timer = 0;
rep(v, 0, N + M){
if(dsu.find(v) == v){
dfs(v, -1);
}
}
vector<pii> p1(N + M);
rep(v, 0, N + M){
p1[v] = {tin[v], tou[v]};
}
rep(i, 0, N + M){
g[i].clear();
}
dsu.init(N + M); root = N;
rep(i, 0, Q){
q[R[i]].pb(i);
}
vector<int> b(Q);
rep(r, 0, N){
for(int u : edge[r]){
if(u <= r)
add_edge(r, u);
}
for(int i : q[r]){
b[i] = dsu.find(E[i]);
}
q[r].clear();
}
timer = 0;
rep(v, 0, N + M){
if(dsu.find(v) == v){
dfs(v, -1);
}
}
vector<pii> p2(N + M);
rep(v, 0, N + M){
p2[v] = {tin[v], tou[v]};
}
vector<int> y(N + M, -1);
rep(v, 0, N){
y[p1[v].ff] = p2[v].ff;
}
MergeSortTree mst(N + M, y);
vector<int> ans(Q);
rep(i, 0, Q){
int s = a[i], t = b[i];
ans[i] = mst.query(0, 0, N + M - 1, p1[s].ff, p1[s].ss, p2[t].ff, p2[t].ss);
}
return ans;
}
Compilation message
werewolf.cpp:23:15: error: ISO C++ forbids declaration of 'init' with no type [-fpermissive]
23 | init(int n){
| ^
werewolf.cpp: In member function 'int Dsu::init(int)':
werewolf.cpp:26:5: warning: no return statement in function returning non-void [-Wreturn-type]
26 | }
| ^
