Submission #115683

#	Time	Username	Problem	Language	Result	Execution time	Memory
115683		tinjyu	Werewolf (IOI18_werewolf)	C++14	15 / 100	370 ms	30584 KiB

werewolf

#include "werewolf.h"
#include <iostream>
using namespace std;
long long int ma[400005],t[400005][3],road[200005],map[400005][2],tag[200005][2],pointsum[200005],mintree[5000005],maxtree[5000005],st,en;
int buildmin(int s,int e,int t)
{
	if(s==e)return mintree[t]=ma[s];
	else return mintree[t]=min(buildmin(s,(s+e)/2,t*2),buildmin((s+e)/2+1,e,t*2+1));
}
int buildmax(int s,int e,int t)
{
	if(s==e)return maxtree[t]=ma[s];
	else return maxtree[t]=max(buildmax(s,(s+e)/2,t*2),buildmax((s+e)/2+1,e,t*2+1));
}
int findmin(int s,int e,int t)
{
	if(en<s || st>e)return 99999999;
	else if(st<=s && e<=en)return mintree[t];
	else return min(findmin(s,(s+e)/2,t*2),findmin((s+e)/2+1,e,t*2+1));
}
int findmax(int s,int e,int t)
{
	//cout<<s<<" "<<e<<" "<<t<<" "<<maxtree[t]<<endl;
	if(en<s || st>e)return -1;
	else if(st<=s && e<=en)return maxtree[t];
	else return max(findmax(s,(s+e)/2,t*2),findmax((s+e)/2+1,e,t*2+1));
}
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) {
	int q = s.size();
	int m = x.size();
	std::vector<int> a(q);
	for(int i=0;i<n;i++)road[i]=-1;
	for(int i=0;i<m;i++)
	{
		pointsum[x[i]]++;
		pointsum[y[i]]++;
		map[i*2][0]=x[i];
		map[i*2][1]=road[y[i]];
		road[y[i]]=i*2;
		map[i*2+1][0]=y[i];
		map[i*2+1][1]=road[x[i]];
		road[x[i]]=i*2+1;
	}
	int one=0,two=0,start=-1,end=-1;
	for(int i=0;i<n;i++)
	{
		if(pointsum[i]==1)
		{
			one++;
			if(start==-1)start=i;
			else end=i;
		}
		if(pointsum[i]==2)two++;
	}
	//cout<<endl;
	if(one==2 && two+one==n && n==m+1)
	{
		int question=q;
		int tag[200005];
		int q=road[start];
		ma[1]=start;
		tag[start]=1;
		for(int i=2;i<=n;i++)
		{
			if(tag[map[q][0]]==0)
			{
				tag[map[q][0]]=i;
				ma[i]=map[q][0];
				q=road[map[q][0]];
			}
			else
			{
				q=map[q][1];
				tag[map[q][0]]=i;
				ma[i]=map[q][0];
				q=road[map[q][0]];
			}
		}
		//for(int i=1;i<=n;i++)cout<<ma[i]<<" ";
		//cout<<endl;
		buildmin(1,n,1);
		buildmax(1,n,1);
		for(int i=0;i<question;i++)
		{
			int c=0;
			st=tag[s[i]],en=tag[e[i]];
			if(st>en)
			{
				swap(st,en);
				c=1;
			}
			int tmpstart=st,tmpend=en;
			int left=st,right=en;
			while(left<=right)
			{
				int mi,maxp,mid=(left+right)/2;
				st=tmpstart;
				en=mid;
				//cout<<"找最小"<<st<<" "<<en<<" "<<endl;
				if(c==0)mi=findmin(1,n,1);
				else maxp=findmax(1,n,1);
				//for(int j=st;j<=en;j++)cout<<ma[j]<<" ";
				//cout<<endl;
				en=tmpend;
				st=mid;
				//cout<<"找最大"<<st<<" "<<en<<" "<<endl;
				if(c==0)maxp=findmax(1,n,1);
				else mi=findmin(1,n,1);
				//for(int j=st;j<=en;j++)cout<<ma[j]<<" ";
				//cout<<endl;
				//cout<<mi<<" "<<maxp<<endl;
				if(c==0)
				{
					if(mi>=l[i] && maxp<=r[i])
					{
						a[i]=1;
						break;
					}
					else if(mi<l[i])right=mid-1;
					else left=mid+1;
				}
				else
				{
					if(mi>=l[i] && maxp<=r[i])
					{
						a[i]=1;
						break;
					}
					else if(mi<l[i])left=mid+1;
					else right=mid-1;
				}
			}
			//cout<<i<<endl;
		}
		//cout<<"finish"<<endl;
		return a;
	}
	int ans;
	for(int i=0;i<q;i++)
	{
		ans=0;
		for(int j=0;j<n;j++)
		{
			tag[j][0]=0;
			tag[j][1]=0;
		}
		int people=l[i],wolf=r[i],start=s[i],end=e[i];
		tag[start][0]=1;
		t[1][0]=start;
		t[1][1]=0;
		t[1][2]=-1;
		int p=1,pp=1;
		while(p<=pp)
		{
			int now=t[p][0],mode=t[p][1];
			int g=road[now];
			if(now==45 && mode==1 && i==55)
			{
				int z=p;
				while(z!=-1)
				{
					z=t[z][2];
				}
			}
			if(now<=wolf && now>=people && t[p][1]==0 && tag[now][1]==0)
			{
 
					pp++;
					t[pp][0]=now;
					t[pp][1]=1;
					t[pp][2]=p;
					tag[now][1]=1;
				
			}
			while(g!=-1)
			{
				if(tag[map[g][0]][mode]==0 && ((mode==0 && map[g][0]>=people) || (mode==1 && map[g][0]<=wolf)))
				{
					pp++;
					t[pp][0]=map[g][0];
					t[pp][1]=mode;
					t[pp][2]=p;
					tag[map[g][0]][mode]=1;
				}
				g=map[g][1];
			}
			p++;
		}
		a[i]=tag[end][1];
	}
	return a;
}

Compilation message (stderr)

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:44:27: warning: variable 'end' set but not used [-Wunused-but-set-variable]
  int one=0,two=0,start=-1,end=-1;
                           ^~~
werewolf.cpp:138:6: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
  int ans;
      ^~~

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