Submission #96691

#	Time	Username	Problem	Language	Result	Execution time	Memory
96691		diamond_duke	Werewolf (IOI18_werewolf)	C++11	100 / 100	1453 ms	177112 KiB

werewolf

#include "werewolf.h"
#include <algorithm>
#include <utility>
namespace DSU
{
	int fa[600005];
	inline void init(int n) { for (int i = 0; i < n; i++) fa[i] = i; }
	int getfa(int u) { return u == fa[u] ? u : fa[u] = getfa(fa[u]); }
}
struct Tree
{
	int fa[600005][25], val[600005], st[600005], en[600005], clk;
	std::vector<int> son[600005];
	void dfs(int u, int f = -1)
	{
		fa[u][0] = f;
		for (int i = 1; i < 20; i++)
			fa[u][i] = fa[u][i - 1] == -1 ? -1 : fa[fa[u][i - 1]][i - 1];
		st[u] = clk++;
		for (int v : son[u])
			dfs(v, u);
		en[u] = clk - 1;
	}
	template <typename funcT>
	inline void init(int n, std::vector<int> &eu, std::vector<int> &ev, funcT func)
	{
		int m = eu.size();
		DSU::init(n + m);
		std::vector<int> edge(m);
		for (int i = 0; i < m; i++)
			edge[i] = i;
		std::sort(edge.begin(), edge.end(), [&] (int x, int y) { return func(x) > func(y); });
		int cur = n;
		for (int e : edge)
		{
			int u = DSU::getfa(eu[e]), v = DSU::getfa(ev[e]);
			if (u == v)
				continue;
			DSU::fa[u] = DSU::fa[v] = cur;
			son[cur].push_back(u);
			son[cur].push_back(v);
			val[cur++] = func(e);
		}
		dfs(cur - 1);
	}
	inline std::pair<int, int> query(int u, int x)
	{
		for (int i = 19; i >= 0; i--)
		{
			if (~fa[u][i] && val[fa[u][i]] >= x)
				u = fa[u][i];
		}
		return {st[u], en[u]};
	}
} human, werewolf;
int BIT[600005], LIM = 6e5 + 2;
inline void modify(int pos)
{
	for (pos++; pos <= LIM; pos += pos & -pos)
		BIT[pos]++;
}
inline int query(int pos)
{
	int res = 0;
	for (pos++; pos; pos -= pos & -pos)
		res += BIT[pos];
	return res;
}
std::vector<int> check_validity(int n, std::vector<int> eu, std::vector<int> ev,
								std::vector<int> qu, std::vector<int> qv,
								std::vector<int> ql, std::vector<int> qr)
{
	int q = qu.size();
	human.init(n, eu, ev, [&] (int x) { return std::min(eu[x], ev[x]); });
	werewolf.init(n, eu, ev, [&] (int x) { return -std::max(eu[x], ev[x]); });
	std::vector<std::vector<std::pair<int, int> > > vec(human.clk);
	for (int i = 0; i < q; i++)
	{
		auto x = human.query(qu[i], ql[i]), y = werewolf.query(qv[i], -qr[i]);
		int l = x.first, r = x.second, L = y.first, R = y.second;
		vec[l].emplace_back(R, i);
		if (L)
			vec[l].emplace_back(L - 1, ~i);
		if (r + 1 < human.clk)
		{
			vec[r + 1].emplace_back(R, ~i);
			if (L)
				vec[r + 1].emplace_back(L - 1, i);
		}
	}
	std::vector<int> val(human.clk, -1), ans(q);
	for (int i = 0; i < n; i++)
		val[human.st[i]] = werewolf.st[i];
	for (int i = human.clk - 1; i >= 0; i--)
	{
		if (~val[i])
			modify(val[i]);
		for (auto &it : vec[i])
		{
			int res = query(it.first), x = it.second;
			if (x >= 0)
				ans[x] += res;
			else
				ans[~x] -= res;
		}
	}
	for (int i = 0; i < q; i++)
		ans[i] = (bool)ans[i];
	return ans;
}

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