Submission #126053

#	Time	Username	Problem	Language	Result	Execution time	Memory
126053		arthurconmy	Werewolf (IOI18_werewolf)	C++14	15 / 100	985 ms	27900 KiB

werewolf

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>

#ifndef ARTHUR_LOCAL
	#include "werewolf.h"
#endif

using namespace std;

using vi = vector<int>;

#define REP(i,a,b) \
for(int i=int(a); i<=int(b); i++)

#define REPb(i,a,b) \
for(int i=int(a); i>=int(b); i--)

#define pb push_back

// ALL THE STUFF FROM ST1 and ST2

const int MAXN = int(2e5)+1;
bool human_vis[MAXN];
bool wolf_vis[MAXN];
vi adj[MAXN];
bool works=false;
int l=-1;
int r=-1;

int arr[MAXN];
int inv[MAXN];

int st[2][524288];
const int p2=262144;

const int INF=int(1e9);

void human_dfs(int u)
{
	// cout << "HUMAN DFS AT " << u << endl;

	human_vis[u]=1;

	for(auto v:adj[u])
	{
		if(human_vis[v] || v < l) continue;
		human_dfs(v);
	}
}

void wolf_dfs(int u)
{
	wolf_vis[u]=1;

	if(works || human_vis[u])
	{
		works=1;
		return;
	}

	for(auto v:adj[u])
	{
		if(wolf_vis[v] || v > r) continue;
		wolf_dfs(v);
	}
}

void build(int n)
{
	REP(i,0,n-1)
	{
		st[0][i+p2]=arr[i];
		st[1][i+p2]=arr[i];
	}

	REP(i,n,p2-1)
	{
		st[0][i+p2]=INF;
	}

	REPb(i,p2-1,1)
	{
		st[0][i]=min(st[0][2*i],st[0][i+i+1]);
		st[1][i]=max(st[1][i+i],st[1][i+i+1]);
	}
}

int query(bool b, int l, int r)
{
	l+=p2;
	r+=p2;

	int ans=0;
	if(!b) ans=int(1e9);

	while(l<=r)
	{
		if(l%2 == 1)
		{
			if(b) ans=max(ans,st[b][l++]);
			else ans=min(ans,st[b][l++]);
		}

		if(r%2 == 0)
		{
			if(b) ans=max(ans,st[b][r--]);
			else ans=min(ans,st[b][r--]);
		}

		l/=2;
		r/=2;
	}

	return ans;
}

vi check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R) 
{
 	int M = X.size();
 	int Q = S.size();

 	#ifdef ARTHUR_LOCAL
 		M=100000;
 	#endif

 	if(n<=3000 && M<=6000 && Q<=3000)
 	{
	 	REP(i,0,M-1)
	 	{
	 		adj[X[i]].pb(Y[i]);
	 		adj[Y[i]].pb(X[i]);
	 	}

	 	vi ans;

	 	REP(q,0,Q-1)
	 	{
	 		REP(i,0,MAXN-1)
	 		{
	 			human_vis[i]=0;
	 			wolf_vis[i]=0;
	 		}

	 		// cout << "DONE" << endl;

	 		works=0;
	 		l=L[q];
	 		r=R[q];

	 		human_dfs(S[q]);
	 		wolf_dfs(E[q]);

	 		if(works) ans.pb(1);
	 		else ans.pb(0);
	 	}

	 	return ans;
	}

	REP(i,0,n-2)
	{
		adj[X[i]].pb(Y[i]);
		adj[Y[i]].pb(X[i]);
	
		// cout << X[i] << " " << Y[i] << endl;
	}

	REP(i,0,n-1)
	{
		if(adj[i].size()==1)
		{
			arr[0]=i;
			arr[1]=adj[i][0];
			break;
		}
	}

	REP(i,2,n-1)
	{
		if(adj[arr[i-1]][0] != arr[i-2]) arr[i]=adj[arr[i-1]][0];
		else arr[i]=adj[arr[i-1]][1];
	}

	REP(i,0,n-1)
	{
		inv[arr[i]]=i;
	}

	build(n);

	// cout << query(0,0,5) << endl; // looks like query does what it says on the tin

	vi ans;

	REP(q,0,Q-1)
	{
		int start = inv[S[q]];
		int end = inv[E[q]];

		l=L[q];
		r=R[q];

		// cout << start << " " << end << " " << l << " " << r << endl;

		// cout << arr[end] << " " << r << endl;

		if(arr[start]<l || arr[end]>r)
		{
			ans.pb(0);
			continue;
		}

		if(start==end)
		{
			if(l<=arr[start] && r>=arr[start]) ans.pb(1);
			else ans.pb(0);
			continue;
		}

		if(start<end)
		{
			// bin search forwards from start

			int lo=start;
			int hi=end;

			while(lo<hi)
			{
				int mid=(lo+hi)/2;

				if(query(0,start,mid)>=l)
				{
					if(hi==lo+1) // stops infinite loop thing
					{
						if(query(0,start,hi)>=l) lo=hi;
						else hi=lo;
					}

					else lo=mid;
				}

				else
				{
					hi=mid-1;
				}
			}

			int max_travel_human = lo;
			
			// bin search backwards from end

			lo=start;
			hi=end;

			while(lo<hi)
			{
				int mid=(lo+hi)/2;

				if(query(1,mid,end)<=r)
				{
					if(hi==lo+1)
					{
						if(query(1,hi,end)<=r) hi=lo;
						else lo=hi;
					}

					else hi=mid;
				}

				else
				{
					lo=mid+1;
				}
			}

			int min_travel_werewolf = lo;

			// cout << min_travel_werewolf << " " << max_travel_human << endl;

			if(min_travel_werewolf <= max_travel_human) ans.pb(1);
			else ans.pb(0);
		}

		else // end < start
		{
			// reverse human and werewolf parts here

			// cout << "HERE" << endl;

			int lo=end;
			int hi=start;

			while(lo<hi)
			{
				// cout << lo << " " << hi << endl;

				int mid=(lo+hi)/2;

				if(query(1,start,mid)<=r)
				{
					if(hi==lo+1) // stops infinite loop thing
					{
						if(query(1,start,hi)<=r) lo=hi;
						else hi=lo;
					}

					else lo=mid;
				}

				else
				{
					hi=mid-1;
				}
			}

			int max_travel_wolf = lo;
			
			// bin search backwards from end

			lo=start;
			hi=end;

			while(lo<hi)
			{
				int mid=(lo+hi)/2;

				if(query(0,mid,end)>=l)
				{
					if(hi==lo+1)
					{
						if(query(0,hi,end)>=l) hi=lo;
						else lo=hi;
					}

					else hi=mid;
				}

				else
				{
					lo=mid+1;
				}
			}

			int min_travel_human = lo;

			// cout << min_travel_human << " " << max_travel_wolf << endl;

			if(min_travel_human <= max_travel_wolf) ans.pb(1);
			else ans.pb(0);
		}
	}

	return ans;
}

// int main()
// {
// 	vi ans = check_validity(6,{4,3,0,2,1},{2,1,4,3,5},{4,4,5},{1,2,4},{2,2,3},{3,2,4});

// 	for(auto a:ans)
// 	{
// 		cout << a << " ";
// 	}
// 	cout << endl;
// }

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