oj.uz

Submission #115655

# Submission time Handle Problem Language Result Execution time Memory
115655 2019-06-08T13:05:19 Z tinjyu Werewolf (IOI18_werewolf) C++14
0 / 100
 233 ms 36608 KB 
#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[500005],maxtree[500005],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 mintree[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)
{
	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]];
			}
		}
		buildmin(1,n,1);
		buildmax(1,n,1);
		for(int i=0;i<question;i++)
		{
			st=tag[s[i]],en=tag[e[i]];
			if(st>en)swap(st,en);
			int tmpstart=st,tmpend=en;
			int left=st,right=en;
			while(left<=right)
			{
				int mid=(left+right)/2;
				st=tmpstart;
				en=mid;
				//cout<<"找最小"<<st<<" "<<en<<" "<<endl;
				int mi=findmin(1,n,1);
				
				en=tmpend;
				st=mid;
				//cout<<"找最大"<<st<<" "<<en<<" "<<endl;
				int ma=findmax(1,n,1);
			//	cout<<mi<<" "<<ma<<endl;
				//cout<<"ok"<<endl;
				if(mi>=l[i] && ma<=r[i])
				{
					a[i]=1;
					break;
				}
				else if(mi<l[i])right=mid-1;
				else left=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

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Incorrect 2 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Incorrect 2 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 233 ms 36608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Incorrect 2 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -