Submission #433977

#	Time	Username	Problem	Language	Result	Execution time	Memory
433977		frodakcin	Werewolf (IOI18_werewolf)	C++11	15 / 100	4054 ms	39652 KiB

werewolf

#include "werewolf.h"
#include <algorithm>
#include <functional>

template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}

const int MN = 2e5+10;
const int MQ = 2e5+10;

struct DSU
{
	int S;
	std::vector<int> p, r;
	DSU(int _S): S(_S), p(_S, -1), r(_S, 0) {}
	int find(int n) {return p[n]==-1 ? n : p[n] = find(p[n]);}
	bool merge(int a, int b)
	{
		a=find(a), b=find(b);
		if(a==b) return 0;
		if(r[a]<r[b]) std::swap(a,b);
		p[b]=a, r[a]+=r[a]==r[b], r[b]=-1;
		return 1;
	}
};

int N, M, Q;
std::vector<int> a0[MN], a[MN], ans;

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
	::N=N;
	M=X.size();
	Q = S.size();

	ans.assign(Q, 0);

	for(int i=0;i<M;++i)
	{
		a0[X[i]].push_back(Y[i]);
		a0[Y[i]].push_back(X[i]);
	}
	DSU dsu(N);
	for(int i=0;i<N;++i)
	{
		std::sort(a0[i].begin(), a0[i].end(), std::greater<int>());
		for(int x:a0[i])
			if(x<i && dsu.merge(x, i))
				a[x].push_back(i), a[i].push_back(x);
	}

	for(int i=0;i<Q;++i)
	{
		std::vector<char> vh(N, 0), vw(N, 0);

		std::function<void(int)> dfs=[&](int n)
		{
			vh[n]=1;
			for(int x:a0[n])
				if(!vh[x] && x >= L[i])
					dfs(x);
		};
		dfs(S[i]);

		dfs = [&](int n)
		{
			vw[n]=1;
			for(int x:a0[n])
				if(!vw[x] && x <= R[i])
					dfs(x);
		};
		dfs(E[i]);

		for(int j=0;!ans[i] && j<N;++j)
		{
			//printf("%d: %d: [%d/%d]\n", i, j, vh[j], vw[j]);
			ans[i] |= vh[j] && vw[j];
		}
	}
  return ans;
}

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