Submission #1198251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198251		dubabuba	Werewolf (IOI18_werewolf)	C++20	Compilation error	0 ms	0 KiB

werewolf

#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