Submission #592832

#	Time	Username	Problem	Language	Result	Execution time	Memory
592832		Temmie	Werewolf (IOI18_werewolf)	C++17	0 / 100	383 ms	524288 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

struct Dsu {
	
	std::vector <int> p;
	std::vector <int> cs;
	
	inline Dsu(int s) {
		cs.resize(s, 1);
		p.resize(s);
		std::iota(p.begin(), p.end(), 0);
	}
	
	inline Dsu(const Dsu& dsu) {
		p = dsu.p;
		cs = dsu.cs;
	}
	
	inline int find(int v) {
		return v == p[v] ? v : (p[v] = find(p[v]));
	}
	
	inline void unite(int u, int v) {
		u = find(u);
		v = find(v);
		if (cs[u] > cs[v]) {
			p[v] = u;
			cs[u] += cs[v];
		} else {
			p[u] = v;
			cs[v] += cs[u];
		}
	}
	
	friend std::ostream& operator << (std::ostream& stream, Dsu dsu) {
		stream << "{ ";
		for (int i = 0; i < (int) dsu.p.size(); i++) {
			stream << dsu.find(i) << " ";
			if (i + 1 == (int) dsu.p.size()) {
				stream << "}";
			}
		}
		return stream;
	}
	
};

struct Block {
	
	int from, to;
	Dsu dsu;
	std::vector <int> my_comp_to_main;
	
	Block() : from(-1), to(-1), dsu(0), my_comp_to_main(0) { }
	
	Block(int _from, int _to, const Dsu& _dsu) :
	from(_from), to(_to), dsu(_dsu), my_comp_to_main(_dsu.p.size(), -1) { }
	
	constexpr int idx_to_cdx(int ind) const {
		return ind - from;
	}
	
	constexpr int cdx_to_ind(int cdx) const {
		return cdx + from;
	}
	
};

constexpr const int BS = 600;

struct Query {
	
	int i, s, e, l, r;
	
};

std::vector <int> check_validity(int n, std::vector <int> _u, std::vector <int> _v,
std::vector <int> s, std::vector <int> e, std::vector <int> l, std::vector <int> r) {
	int m = _u.size();
	int q = s.size();
	std::vector <std::vector <int>> g(n);
	std::vector <int> deg(n, 0);
	for (int i = 0; i < m; i++) {
		g[_u[i]].push_back(_v[i]);
		g[_v[i]].push_back(_u[i]);
		deg[_u[i]]++;
		deg[_v[i]]++;
	}
	int acu = 0;
	std::vector <int> block_start;
	for (int i = 0; i < n; i++) {
		acu += deg[i];
		if (acu >= BS) {
			block_start.push_back(i);
			acu = 0;
		}
	}
	if (acu) {
		block_start.push_back(n - 1);
	}
	std::vector <Block> blocks(block_start.size());
	{
		Dsu dsu(n);
		for (int i = n - 1, bs_ptr = (int) block_start.size() - 1; bs_ptr >= 0 && i >= 0; i--) {
			for (int x : g[i]) {
				if (x >= i) {
					dsu.unite(i, x);
				}
			}
			if (block_start[bs_ptr] == i) {
				blocks[bs_ptr] =
				Block(bs_ptr ? block_start[bs_ptr - 1] + 1 : 0, block_start[bs_ptr], dsu);
				bs_ptr--;
			}
		}
	}
	std::vector <std::vector <Query>> ques(n);
	for (int i = 0; i < q; i++) {
		ques[r[i]].push_back({ i, s[i], e[i], l[i], r[i] });
	}
	Dsu dsu(n);
	std::vector <int> ans(q, 0);
	for (int i = 0; i < n; i++) {
		for (int x : g[i]) {
			if (x <= i) {
				dsu.unite(i, x);
				int v = dsu.find(i);
				for (Block& block : blocks) {
					if (block.to > i) {
						break;
					}
					block.my_comp_to_main[block.dsu.find(i)] = v;
					block.my_comp_to_main[block.dsu.find(x)] = v;
				}
			}
		}
		for (const Query& que : ques[i]) {
			assert(que.r == i);
			int bid = std::lower_bound(blocks.begin(), blocks.end(), que.l,
			[] (const Block& u, const int& v) { return u.to < v; }) - blocks.begin();
			if (blocks[bid].my_comp_to_main[blocks[bid].dsu.find(que.s)] == dsu.find(que.e)) {
				ans[que.i] = 1;
				continue;
			}
			assert(blocks[bid].from <= que.s);
			Dsu cdsu(blocks[bid].to - blocks[bid].from + 1);
			std::vector <bool> cgood(blocks[bid].to - blocks[bid].from + 1, false);
			std::vector <bool> cgood_s(blocks[bid].to - blocks[bid].from + 1, false);
			for (int j = blocks[bid].to; j >= que.l; j--) {
				if (dsu.find(j) == dsu.find(que.e)) {
					cgood[cdsu.find(blocks[bid].idx_to_cdx(j))] = true;
				}
				for (int x : g[j]) {
					if (x >= j) {
						if (x <= blocks[bid].to && dsu.find(x) == dsu.find(que.e)) {
							cgood[cdsu.find(blocks[bid].idx_to_cdx(x))] = true;
						}
						if (blocks[bid].my_comp_to_main[blocks[bid].dsu.find(x)] == dsu.find(que.e)) {
							cgood[cdsu.find(blocks[bid].idx_to_cdx(j))] = true;
						}
						if (blocks[bid].dsu.find(que.s) == blocks[bid].dsu.find(x)) {
							cgood_s[cdsu.find(blocks[bid].idx_to_cdx(j))] = true;
						}
						if (x <= blocks[bid].to) {
							int u = cdsu.find(blocks[bid].idx_to_cdx(j));
							int v = cdsu.find(blocks[bid].idx_to_cdx(x));
							cgood[u] = cgood[v] = cgood[u] | cgood[v];
							cgood_s[u] = cgood_s[v] = cgood_s[u] | cgood_s[v];
							cdsu.unite(u, v);
						}
					}
				}
			}
			for (int j = blocks[bid].to; j >= que.s; j--) {
				if (cgood[cdsu.find(blocks[bid].idx_to_cdx(j))] &&
				cgood_s[cdsu.find(blocks[bid].idx_to_cdx(j))]) {
					ans[que.i] = 1;
					break;
				}
			}
		}
	}
	return ans;
}

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