oj.uz

Submission #115659

# Submission time Handle Problem Language Result Execution time Memory
115659 2019-06-08T13:47:07 Z tinjyu Werewolf (IOI18_werewolf) C++14
15 / 100
 367 ms 30200 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 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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 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 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 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 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 367 ms 1000 KB Output is correct
11 Correct 231 ms 1016 KB Output is correct
12 Correct 13 ms 1024 KB Output is correct
13 Correct 291 ms 896 KB Output is correct
14 Correct 208 ms 1016 KB Output is correct
15 Correct 286 ms 1144 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 220 ms 30200 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 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 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 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 367 ms 1000 KB Output is correct
11 Correct 231 ms 1016 KB Output is correct
12 Correct 13 ms 1024 KB Output is correct
13 Correct 291 ms 896 KB Output is correct
14 Correct 208 ms 1016 KB Output is correct
15 Correct 286 ms 1144 KB Output is correct
16 Incorrect 220 ms 30200 KB Output isn't correct
17 Halted 0 ms 0 KB -