#include <bits/stdc++.h>
#include "werewolf.h"
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
const int MAX_N = 9e4 + 1;
bitset<MAX_N> component0[2 * MAX_N];
bitset<MAX_N> component1[2 * MAX_N];
struct Dsu {
int n, ind;
vi loga;
vi par, t;
vvi dp;
Dsu() {}
Dsu(int n, int ind): n(n), ind(ind) {
par.resize(n), t.resize(n);
dp.resize(1, vi(n));
for (int i = 0; i < n; i++) {
dp[0][i] = i;
if (!ind) {
component0[i][i] = true;
} else component1[i][i] = true;
}
iota(all(par), 0);
}
inline void Add(int time) {
par.push_back(n);
t.push_back(time);
dp[0].push_back(n);
n++;
}
int Find(int i) {
return par[i] == i ? i : par[i] = Find(par[i]);
}
void Union(int a, int b, int time) {
int pa = Find(a), pb = Find(b);
if (pa == pb) return;
Add(time);
par[pa] = par[pb] = n - 1;
dp[0][pa] = dp[0][pb] = n - 1;
if (!ind) {
component0[n - 1] = component0[pa] | component0[pb];
} else {
component1[n - 1] = component1[pa] | component1[pb];
}
}
void Build() {
loga.resize(n + 1);
for (int i = 2; i <= n; i++) loga[i] = loga[i >> 1] + 1;
dp.resize(loga[n] + 1, vi(n));
for (int i = n - 1; i >= 0; i--) {
for (int j = 1; j <= loga[n]; j++) {
dp[j][i] = dp[j - 1][dp[j - 1][i]];
}
}
}
int Jump(int node, int time) {
for (int i = loga[n]; i >= 0; i--) {
if (t[dp[i][node]] <= time) {
node = dp[i][node];
}
}
return node;
}
};
int ind[MAX_N];
vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r) {
int m = x.size();
Dsu d_min(n, 0), d_max(n, 1);
iota(ind, ind + m, 0);
sort(ind, ind + m, [&] (int i, int j) {
return max(x[i], y[i]) < max(x[j], y[j]);
});
for (int i = 0; i < m; i++) {
d_min.Union(x[ind[i]], y[ind[i]], max(x[ind[i]], y[ind[i]]));
}
d_min.Build();
sort(ind, ind + m, [&] (int i, int j) {
return min(x[i], y[i]) > min(x[j], y[j]);
});
for (int i = 0; i < m; i++) {
d_max.Union(x[ind[i]], y[ind[i]], n - min(x[ind[i]], y[ind[i]]));
}
d_max.Build();
int q = s.size();
vi ans(q);
for (int i = 0; i < q; i++) {
int time_max = n - l[i], time_min = r[i];
int v_max = d_max.Jump(s[i], time_max);
int v_min = d_min.Jump(e[i], time_min);
ans[i] = (component0[v_min] & component1[v_max]).any();
}
return ans;
}
//6 6 3
//0 3
//1 2
//1 5
//1 3
//2 5
//3 4
//
//4 2 1 2
//4 2 2 2
//5 4 3 4
//6 5 3
//1 3
//3 0
//0 4
//4 5
//5 2
//
//3 5 0 5
//2 1 0 4
//4 2 3 4
Compilation message
/tmp/ccJqmzGB.o: in function `_GLOBAL__sub_I_component0':
werewolf.cpp:(.text.startup+0xb): relocation truncated to fit: R_X86_64_PC32 against `.bss'
werewolf.cpp:(.text.startup+0x29): relocation truncated to fit: R_X86_64_PC32 against `.bss'
/usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(vterminate.o): in function `__gnu_cxx::__verbose_terminate_handler()':
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x1e): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x2b): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
