Submission #805986

#	Time	Username	Problem	Language	Result	Execution time	Memory
805986		LIF	Werewolf (IOI18_werewolf)	C++14	49 / 100	879 ms	72684 KiB

werewolf

#include "werewolf.h"
#include<vector>
#include<bits/stdc++.h>
#include<queue>
using namespace std;
int pos[300005];
int ind[300005];
int id[300005];
int val[300005];
vector<int> ans;
vector<int> vv[300005];
int stmin[200005][23];
int stmax[200005][23];
bool flag1[400005];
bool vis[300005];
bool flag2[300005];
bool vis2[30005];
void dfs(int now,int num)
{
	//cout<<now<<" "<<num<<endl;
	vis[now] = true;
	id[now] = num;
	val[num] = now;
	for(int i=0;i<vv[now].size();i++)
	{
		int to = vv[now][i];
		if(vis[to] == false)dfs(to,num+1);
	}
	return;
}
int checkmin(int x,int y)
{
	int len = log(y-x+1) / log(2);
	return min(stmin[x][len],stmin[y-(1<<(len))+1][len]); 
}
int checkmax(int x,int y)
{
	int len = log(y-x+1) / log(2);
	return max(stmax[x][len],stmax[y-(1<<(len))+1][len]);
}
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)
{
	if(N <= 3000)
	{
		for(int i=0;i<X.size();i++)
		{
			vv[X[i]].push_back(Y[i]);
			vv[Y[i]].push_back(X[i]);
		}
		for(int i=0;i<S.size();i++)
		{	
			queue<int> q;
			for(int j=0;j<N;j++)flag1[j] = false;
			for(int j=0;j<N;j++)flag2[j] = false;
			for(int j=0;j<N;j++)vis[j] = false;
			for(int j=0;j<N;j++)vis2[j] = false;
			q.push(S[i]);
			flag1[S[i]] = true;
			while(q.empty() == false)
			{
				//cout<<"yeah"<<endl;
				int xx = q.front();
				q.pop();
				if(vis[xx] == true)continue;
				vis[xx] = true;
				for(int j=0;j<vv[xx].size();j++)
				{
					int to = vv[xx][j];
					if(to >= L[i])
					{
						flag1[to] = true;
					//	vis[to] = true;
						q.push(to);
					}
				}
			}
			//cout<<"YEAH"<<endl;
			q.push(E[i]);
			flag2 [E[i]] = true;
			while(q.empty() == false)
			{
				int xx = q.front();
				q.pop();
				//cout<<xx<<endl;
				if(vis2[xx] == true)continue;
				vis2[xx] = true;
				for(int j=0;j<vv[xx].size();j++)
				{
					int to = vv[xx][j];
					if(to <= R[i])
					{
						flag2[to] = true;
						q.push(to);
					}
				}
			}
			for(int j=0;j<N;j++)
			{
				if(flag1[j] == true && flag2[j] == true && L[i] <= j && j <= R[i])
				{
					ans.push_back(1);
					break;
				}
			}
			if(ans.size() < i+1)ans.push_back(0);
		}
		return ans;
	}
	else
	{
			for(int i=0;i<X.size();i++)
		{
			ind[X[i]]++;ind[Y[i]]++;
			vv[X[i]].push_back(Y[i]);
			vv[Y[i]].push_back(X[i]);
		}
		//cout<<"yeah"<<endl;
		for(int i=0;i<N;i++)
		{
			if(ind[i] != 1)continue;
			dfs(i,0);
			break;
		}
		for(int i=0;i<N;i++)
		{
			stmin[i][0] = val[i];
			stmax[i][0] = val[i];
		}
		for(int i=1;i<=20;i++)
		{
			for(int j=0;j+ (1<<i) - 1< N;j++)
			{
				stmin[j][i] = min(stmin[j][i-1],stmin[j+(1<<(i-1))][i-1]);
				stmax[j][i] = max(stmax[j][i-1],stmax[j+(1<<(i-1))][i-1]);
			}
		}
		/*for(int i=0;i<N;i++)cout<<i<<" ";
		cout<<endl;;
		for(int i=0;i<N;i++)cout<<id[i]<<" ";
		cout<<endl;
		for(int i=0;i<N;i++)cout<<val[i]<<" ";
		cout<<endl;*/
	//	cout<<checkmax(1,5)<<endl;
		for(int i=0;i<S.size();i++)
		{
			int xx = id[S[i]];
			int yy = id[E[i]];
			if(xx < yy)
			{
				int ll = xx;int rr = yy;
				int last1 = xx;
				int last2 = yy;
				while(ll <= rr)
				{
					int mid = (ll+rr)>>1;
					if(checkmin(xx,mid) >= L[i])
					{
						last1 = mid;
						ll = mid + 1;
					}
					else rr = mid - 1;
				}
				ll = xx;rr = yy;
				while(ll <= rr)
				{
					int mid = (ll+rr)>>1;
					if(checkmax(mid,yy) <= R[i])
					{
						last2 = mid;
						rr = mid - 1;
					}
					else ll = mid+1;
				}
				if(last1 >= last2)ans.push_back(1);
				else ans.push_back(0);
		//		cout<<last1<<" "<<last2<<endl;
			}
			else
			{
				swap(xx,yy);
				int ll = xx;int rr = yy;
				int last1 = xx;
				int last2 = yy;
				while(ll <= rr)
				{
					int mid = (ll+rr)>>1;
					if(checkmax(xx,mid) <= R[i])
					{
						last1 = mid;
						ll = mid + 1;
					}
					else rr = mid - 1;
				}
				ll = xx;rr = yy;
				while(ll <= rr)
				{
					int mid = (ll+rr)>>1;
					if(checkmin(mid,yy) >= L[i])
					{
						last2 = mid;
						rr = mid - 1;
					}
					else ll = mid+1;
				}
				if(last1 >= last2)ans.push_back(1);
				else ans.push_back(0);
			}
		}
		return ans;	
	}
}

Compilation message (stderr)

werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:24:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i=0;i<vv[now].size();i++)
      |              ~^~~~~~~~~~~~~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i=0;i<X.size();i++)
      |               ~^~~~~~~~~
werewolf.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int i=0;i<S.size();i++)
      |               ~^~~~~~~~~
werewolf.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int j=0;j<vv[xx].size();j++)
      |                 ~^~~~~~~~~~~~~~
werewolf.cpp:89:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int j=0;j<vv[xx].size();j++)
      |                 ~^~~~~~~~~~~~~~
werewolf.cpp:107:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |    if(ans.size() < i+1)ans.push_back(0);
      |       ~~~~~~~~~~~^~~~~
werewolf.cpp:113:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |    for(int i=0;i<X.size();i++)
      |                ~^~~~~~~~~
werewolf.cpp:146:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |   for(int i=0;i<S.size();i++)
      |               ~^~~~~~~~~

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