Submission #434326

#	Time	Username	Problem	Language	Result	Execution time	Memory
434326		frodakcin	Werewolf (IOI18_werewolf)	C++11	100 / 100	762 ms	78332 KiB

werewolf

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

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;
	DSU(int _S): S(_S), p(_S, -1) {}
	int find(int n) {return p[n]==-1 ? n : p[n] = find(p[n]);}
	bool merge(int a, int b) // b into a
	{
		a=find(a), b=find(b);
		if(a==b) return 0;
		p[b]=a; // no rank
		return 1;
	}
};

struct ST
{
	public:
		int S;
		std::vector<int> v;
		ST(int _S=0): S(_S), v(4*_S, -1) {}

		void upd(int n, int l, int r, int q, int val)
		{
			if(r-l>1)
			{
				int m=l+(r-l)/2;
				if(q < m) upd(n<<1, l, m, q, val);
				else upd(n<<1|1, m, r, q, val);
				v[n]=std::max(v[n<<1], v[n<<1|1]);
			}
			else
				v[n]=val;
		}
		void upd(int q, int val) {upd(1, 0, S, q, val);}

		int qry(int n, int l, int r, int ql, int qr)
		{
			if(ql <= l&&r <= qr) return v[n];
			if(r-l>1)
			{
				int m=l+(r-l)/2, f=-1;
				if(ql < m) ckmax(f, qry(n<<1, l, m, ql, qr));
				if(m < qr) ckmax(f, qry(n<<1|1, m, r, ql, qr));
				return f;
			}
			assert(0);
			return -1;
		}
		int qry(int ql, int qr) {return qry(1, 0, S, ql, qr);}
};

int N, M, Q;
std::vector<int> a[MN], t[2][MN], ans, todo[MN];
int pre[2][MN], post[2][MN], ord[2][MN], ctr[2];

template<int T>
void dfs(int n, int p=-1)
{
	ord[T][ctr[T]]=n;
	pre[T][n]=ctr[T]++;
	for(int x:t[T][n])
		if(x!=p)
			dfs<T>(x, n);
	post[T][n]=ctr[T];
}

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, -1);
	for(int i=0;i<M;++i)
	{
		a[X[i]].push_back(Y[i]);
		a[Y[i]].push_back(X[i]);
	}

	std::vector<int> ss(Q, -1), es(Q, -1); // start/end subtrees

	//human tree
	{
		std::vector<int> ord(Q);
		std::iota(ord.begin(), ord.end(), 0);
		std::sort(ord.begin(), ord.end(), [&](int u, int v){return L[u]>L[v];});
		
		DSU dsu(N);
		for(int i=N-1, j=0;i>=0;--i)
		{
			for(int x:a[i])
			{
				int y=dsu.find(x);
				if(i < x && dsu.merge(i, y))
					t[0][i].push_back(y), t[0][y].push_back(i);
			}
			for(;j < Q && L[ord[j]]==i;++j)
				ss[ord[j]]=dsu.find(S[ord[j]]);
		}
	}
	//werewolf tree
	{
		std::vector<int> ord(Q);
		std::iota(ord.begin(), ord.end(), 0);
		std::sort(ord.begin(), ord.end(), [&](int u, int v){return R[u]<R[v];});

		DSU dsu(N);
		for(int i=0, j=0;i<N;++i)
		{
			for(int x:a[i])
			{
				int y=dsu.find(x);
				if(x < i && dsu.merge(i, y))
					t[1][i].push_back(y), t[1][y].push_back(i);
			}
			for(;j < Q && R[ord[j]]==i;++j)
				es[ord[j]]=dsu.find(E[ord[j]]);
		}
	}

	dfs<0>(0);
	dfs<1>(N-1);

	for(int i=0;i<Q;++i)
		todo[post[1][es[i]]].push_back(i);

	ST segtree(N);
	for(int i=0;i<N;++i)
	{
		segtree.upd(pre[0][ord[1][i]], i); // add ord[1][i]
		for(int x:todo[i+1])
		{
			ans[x] = segtree.qry(pre[0][ss[x]], post[0][ss[x]]) >= pre[1][es[x]];
			//printf("\t%d: %d\n", x, segtree.qry(pre[0][ss[x]], post[0][ss[x]]));
		}
	}

  return ans;
}

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