#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define MP make_pair
const int mxn = 2e5;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef bitset<mxn> bi;
bi hun[mxn], dog[mxn];
int Hans[mxn], Wans[mxn];
int n, m, q;
struct Tree {
int anc[mxn * 2], cnt;
vector<int> chi[mxn * 2];
vector<int> query[mxn * 2];
Tree() { memset(anc, -1, sizeof anc); }
int ancestor(int u) { return anc[u] < 0 ? u : anc[u] = ancestor(anc[u]); }
int unite(int u, int v) {
u = ancestor(u);
v = ancestor(v);
if(u == v) return -1;
anc[cnt] += anc[u];
anc[cnt] += anc[v];
anc[u] = cnt;
anc[v] = cnt;
chi[cnt].push_back(u);
chi[cnt].push_back(v);
return cnt++;
}
bi dfs(int u, bool flag) {
if(u < n) {
bi ret = 0;
ret[u] = 1;
if(flag) {
for(int i : query[u])
hun[i] = ret;
}
else {
for(int i : query[u])
dog[i] = ret;
}
return ret;
}
bi ret = 0;
for(int v : chi[u])
ret |= dfs(v, flag);
if(flag) {
for(int i : query[u])
hun[i] = ret;
}
else {
for(int i : query[u])
dog[i] = ret;
}
return ret;
}
};
Tree humans, wolves;
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
n = N;
m = X.size();
q = S.size();
vector<pii> HQ[n];
vector<pii> WQ[n];
for(int i = 0; i < m; i++) {
int mn = min(X[i], Y[i]);
int mx = max(X[i], Y[i]);
HQ[mn].push_back(MP(-1, mx));
WQ[mx].push_back(MP(-1, mn));
}
for(int i = 0; i < q; i++) {
int l = L[i], r = R[i];
HQ[l].push_back(MP(i, S[i]));
WQ[r].push_back(MP(i, E[i]));
}
// cout << "\nWolves\n";
wolves.cnt = n;
for(int u = 0; u < n; u++) {
for(pii p : WQ[u]) {
int i = p.ff;
int v = p.ss;
if(i == -1) {
int a = wolves.unite(u, v);
// cout << u << ' ' << v << " -> " << a << endl;
}
else {
Wans[i] = wolves.ancestor(v);
wolves.query[Wans[i]].push_back(i);
// cout << "query " << i << ": " << u << ' ' << v << " = " << Wans[i] << endl;
}
}
}
// cout << "\nHumans\n";
humans.cnt = n;
for(int u = n - 1; u >= 0; u--) {
for(pii p : HQ[u]) {
int i = p.ff;
int v = p.ss;
if(i == -1) {
int a = humans.unite(u, v);
// cout << u << ' ' << v << " -> " << a << endl;
}
else {
Hans[i] = humans.ancestor(v);
humans.query[Hans[i]].push_back(i);
// cout << "query " << i << ": " << u << ' ' << n - 1 << " = " << Hans[i] << endl;
}
}
}
bool vis[n * 2];
memset(vis, 0, sizeof vis);
for(int i = 0; i < n; i++) {
int a = wolves.ancestor(i);
if(!vis[a]) {
wolves.dfs(a, 1);
}
}
memset(vis, 0, sizeof vis);
for(int i = 0; i < n; i++) {
int a = humans.ancestor(i);
if(!vis[a]) {
humans.dfs(a, 0);
}
}
vi ret;
bi buba = 0;
for(int i = 0; i < q; i++) {
buba = hun[i] & dog[i];
// cout << S[i] << " -> " << L[i] << ' ' << R[i] << ": ";
// for(int k = 0; k < n; k++)
// cout << hun[i][k];
// cout << endl;
// cout << E[i] << " -> " << L[i] << ' ' << R[i] << ": ";
// for(int k = 0; k < n; k++)
// cout << dog[i][k];
// cout << endl;
if(buba.count())
ret.push_back(1);
else
ret.push_back(0);
// cout << endl;
}
return ret;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
Compilation message (stderr)
/tmp/ccrAQvjz.o: in function `check_validity(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)':
werewolf.cpp:(.text+0x8f9): relocation truncated to fit: R_X86_64_PC32 against symbol `hun' defined in .bss section in /tmp/ccrAQvjz.o
/tmp/ccrAQvjz.o: in function `Tree::dfs(int, bool)':
werewolf.cpp:(.text._ZN4Tree3dfsEib[_ZN4Tree3dfsEib]+0x194): relocation truncated to fit: R_X86_64_PC32 against symbol `hun' defined in .bss section in /tmp/ccrAQvjz.o
werewolf.cpp:(.text._ZN4Tree3dfsEib[_ZN4Tree3dfsEib]+0x24d): relocation truncated to fit: R_X86_64_PC32 against symbol `hun' defined in .bss section in /tmp/ccrAQvjz.o
/tmp/ccrAQvjz.o: in function `_GLOBAL__sub_I_hun':
werewolf.cpp:(.text.startup+0x1a): relocation truncated to fit: R_X86_64_PC32 against `.bss'
/usr/lib/gcc/x86_64-linux-gnu/11/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/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1c): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x60): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x67): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x72): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x87): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x92): additional relocation overflows omitted from the output
(.text._ZNSt8ios_base4InitC2Ev+0x1c6): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x260): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2e2): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x353): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x541): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5e5): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x670): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x6e9): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
/usr/bin/ld: final link failed
collect2: error: ld returned 1 exit status
