Submission #105936

#	Time	Username	Problem	Language	Result	Execution time	Memory
105936		Anai	Werewolf (IOI18_werewolf)	C++14	0 / 100	3269 ms	168804 KiB

werewolf

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

struct Query {
	int start, halt, left, right, idx; };

using pii = pair<int, int>;

const int N = 2e5 + 5;

vector<int> members[N];
map<int, int> dist[N];
int far[N], siz[N], dsu[N], up[N];
unordered_map<int, int> mp[N];

vector<Query> qs;
vector<pii> edgs;
int n, m, q;

static int get_far(int nod) {
	while (far[nod])
		nod = far[nod];
	return nod; }

static bool join(int a, int b) {
	int _up = min(a, b);
	a = get_far(a);
	b = get_far(b);

	if (a == b)
		return false;
	if (siz[b] > siz[a])
		swap(a, b);
	far[b] = a;
	up[b] = _up;
	siz[a]+= siz[b];

	return true; }

static bool magic_join(int a, int b) {
	a = dsu[a];
	b = dsu[b];
	if (a == b)
		return false;
	if (members[b].size() > members[a].size())
		swap(a, b);

	for (auto i: members[b]) {
		dsu[i] = a;
		while (i != 0) {
			auto it = mp[i].find(b);
			if (it == end(mp[i]))
				break;
			auto &ref = mp[i][a];
			ref = max(ref, it->second);
			mp[i].erase(it);
			i = far[i]; } }

	members[a].insert(end(members[a]), begin(members[b]), end(members[b]));
	members[b].clear();
	return true; }

static void build_dsu() {
	sort(begin(edgs), end(edgs), [&](const pii &a, const pii &b) {
		return min(a.x, a.y) > min(b.x, b.y); });

	for (const auto &e: edgs)
		join(e.x, e.y);

	for (int i = 1; i <= n; ++i) {
		int dist = 2e9, nod = i;
		while (nod) {
			mp[nod][i] = dist;
			dist = min(dist, up[nod]);
			nod = far[nod]; } } }

static void initialize() {
	fill(siz, siz + n + 1, 1);
	for (int i = 1; i <= n; ++i) {
		dsu[i] = i;
		mp[i].max_load_factor(0.25);
		members[i].push_back(i); } }

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	vector<int> ant;
	int edg_ptr;
	n = N;
	q = S.size();
	m = X.size();

	qs.resize(q);
	ant.resize(q);
	edgs.resize(m);

	for (int i = 0; i < m; ++i)
		edgs[i] = {X[i] + 1, Y[i] + 1};
	for (int i = 0; i < q; ++i)
		qs[i] = {E[i] + 1, S[i] + 1, L[i] + 1, R[i] + 1, i};

	initialize();
	build_dsu();

	sort(begin(qs), end(qs), [&](const Query &a, const Query &b) { return a.right < b.right; });
	sort(begin(edgs), end(edgs), [&](const pii &a, const pii &b) {
		return max(a.x, a.y) < max(b.x, b.y); });

	edg_ptr = 0;
	for (const auto &query: qs) {
		while (edg_ptr < m && max(edgs[edg_ptr].x, edgs[edg_ptr].y) <= query.right) { // join things accessible in start form
			magic_join(edgs[edg_ptr].x, edgs[edg_ptr].y);
			++edg_ptr; }

		int halt = query.halt, start = query.start, dist = 0;
		while (halt) {
			auto ith = mp[halt].find(dsu[query.halt]), its = mp[halt].find(dsu[query.start]);
			if (ith != end(mp[halt]) && its != end(mp[halt]))
				dist = max(dist, min(its->second, ith->second));
			halt = far[halt]; }

		if (dsu[query.start] == dsu[query.halt] || dist >= query.left)
			ant[query.idx] = 1; }

	return ant; }

#ifdef HOME
int main() {
	ifstream fi("werewolf.in");
	ofstream fo("werewolf.out");
	int n, m, q;

	fi >> n >> m >> q;
	vector<int> x(m), y(m), s(q), e(q), l(q), r(q);
	for (int j = 0; j < m; ++j)
		fi >> x[j] >> y[j];

	for (int i = 0; i < q; ++i)
		fi >> s[i] >> e[i] >> l[i] >> r[i];

	vector<int> ans = check_validity(n, x, y, s, e, l, r);
	for (auto i: ans)
		fo << i << '\n';

	return 0; }
#endif

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:115:26: warning: unused variable 'start' [-Wunused-variable]
   int halt = query.halt, start = query.start, dist = 0;
                          ^~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51