oj.uz

Submission #115683

# Submission time Handle Problem Language Result Execution time Memory
115683 2019-06-08T15:34:47 Z tinjyu Werewolf (IOI18_werewolf) C++14
15 / 100
 370 ms 30584 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[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

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 2 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 3 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 2 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 3 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 370 ms 1032 KB Output is correct
11 Correct 234 ms 896 KB Output is correct
12 Correct 13 ms 896 KB Output is correct
13 Correct 300 ms 1016 KB Output is correct
14 Correct 204 ms 896 KB Output is correct
15 Correct 296 ms 1144 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 223 ms 30584 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 2 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 3 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 370 ms 1032 KB Output is correct
11 Correct 234 ms 896 KB Output is correct
12 Correct 13 ms 896 KB Output is correct
13 Correct 300 ms 1016 KB Output is correct
14 Correct 204 ms 896 KB Output is correct
15 Correct 296 ms 1144 KB Output is correct
16 Incorrect 223 ms 30584 KB Output isn't correct
17 Halted 0 ms 0 KB -