Submission #434022

#	Time	Username	Problem	Language	Result	Execution time	Memory
434022		frodakcin	Werewolf (IOI18_werewolf)	C++11	49 / 100	4040 ms	38836 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;

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

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

		void build(int n, int l, int r, const std::vector<int>& line)
		{
			if(r-l>1)
			{
				int m = l+(r-l)/2;
				build(n<<1, l, m, line);
				build(n<<1|1, m, r, line);
				v[n]=std::min(v[n<<1], v[n<<1|1]);
			}
			else
				v[n]=line[l];
		}
		void build(const std::vector<int>& line) {build(1, 0, S, line);}

		int qryr(int n, int l, int r, int qr, int cut) //rightmost point < cut
		{
			if(v[n]>=cut) return l-1;
			if(r-l>1)
			{
				int m=l+(r-l)/2, f=m-1;
				if(m < qr) f = qryr(n<<1|1, m, r, qr, cut);
				if(f == m-1) return qryr(n<<1, l, m, qr, cut);
				return f;
			}
			return l;
		}
		int qryr(int qr, int cut) {return qryr(1, 0, S, qr, cut);}

		int qryl(int n, int l, int r, int ql, int cut) //leftmost point < cut
		{
			if(v[n]>=cut) return r;
			if(r-l>1)
			{
				int m=l+(r-l)/2, f=m;
				if(ql < m) f = qryl(n<<1, l, m, ql, cut);
				if(f == m) return qryl(n<<1|1, m, r, ql, cut);
				return f;
			}
			return l;
		}
		int qryl(int ql, int cut) {return qryl(1, 0, S, ql, cut);}
};

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)
	{
		a[X[i]].push_back(Y[i]);
		a[Y[i]].push_back(X[i]);
	}

	bool is_line = M+1 == N;
	for(int i=0;i<N && is_line;++i)
		is_line &= a[i].size() <= 2;
	if(is_line)
	{
		int st = -1;
		for(int i=0;st == -1;++i)
			if(a[i].size() == 1) st = i;
		std::vector<int> line, wh(N, -1);
		std::vector<char> vis(N, 0);

		line.push_back(st);
		for(int i=1;i<N;++i)
		{
			int n=line.back();
			vis[n]=1;
			for(int x:a[n])
				if(!vis[x])
					line.push_back(x);
		}
		for(int i=0;i<N;++i) wh[line[i]]=i;

		ST hu(N), ww(N);
		hu.build(line);
		for(int& x:line) x*=-1;
		ww.build(line);

		for(int i=0;i<Q;++i)
		{
			int s=wh[S[i]], e=wh[E[i]];
			if(s<e)
				ans[i]=hu.qryl(s, L[i]) > ww.qryr(e, -R[i])+1;
			else
				ans[i]=ww.qryl(e, -R[i]) > hu.qryr(s, L[i])+1;
		}

		return ans;
	}

	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:a[n])
				if(!vh[x] && x >= L[i])
					dfs(x);
		};
		dfs(S[i]);

		dfs = [&](int n)
		{
			vw[n]=1;
			for(int x:a[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;
}

Compilation message (stderr)

werewolf.cpp: In constructor 'ST::ST(int)':
werewolf.cpp:18:7: warning: 'ST::S' will be initialized after [-Wreorder]
   18 |   int S;
      |       ^
werewolf.cpp:17:20: warning:   'std::vector<int> ST::v' [-Wreorder]
   17 |   std::vector<int> v;
      |                    ^
werewolf.cpp:19:3: warning:   when initialized here [-Wreorder]
   19 |   ST(int _S): S(_S), v(_S*4, 0) {}
      |   ^~

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