Submission #100376

#	Time	Username	Problem	Language	Result	Execution time	Memory
100376		MvC	Werewolf (IOI18_werewolf)	C++11	49 / 100	790 ms	49944 KiB

werewolf

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=2e5+1;
const int mod=1e9+7;
using namespace std;
int n,i,j,t,m,q,l[nmax],r[nmax],s[nmax],e[nmax],id[nmax],bit[nmax],x,y,st,dr,rs,mid,lf[nmax],rg[nmax],v1[3050],v2[3050];
vector<int>g[nmax],vl[nmax],vr[nmax];
void upd(int i)
{
	for(;i<=n;i+=i&(-i))bit[i]++;
}
int qry(int i)
{
	if(!i)return 0;
	int sm=0;
	for(;i>=1;i-=i&(-i))sm+=bit[i];
	return sm;
}
void dfs(int x,int p)
{
	id[x]=id[p]+1;
	for(int i=0;i<g[x].size();i++)
	{
		if(g[x][i]==p)continue;
		dfs(g[x][i],x);
	}
}
void dfs1(int x,int cmp)
{
	v1[x]=1;
	for(int i=0;i<g[x].size();i++)if(g[x][i]>=cmp && !v1[g[x][i]])dfs1(g[x][i],cmp);
}
void dfs2(int x,int cmp)
{
	v2[x]=1;
	for(int i=0;i<g[x].size();i++)if(g[x][i]<=cmp && !v2[g[x][i]])dfs2(g[x][i],cmp);
}
vector<int>check_validity(int N,vector<int>X,vector<int>Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R)
{
	n=N,m=(int)X.size(),q=(int)S.size();
	vector<int>ans;
	for(i=0;i<m;i++)
	{
		x=X[i],y=Y[i];
		x++,y++;
		g[x].pb(y);
		g[y].pb(x);
	}
	if(n<=3000)
	{
		for(i=1;i<=q;i++)
		{
			s[i]=S[i-1],e[i]=E[i-1],l[i]=L[i-1],r[i]=R[i-1];
			s[i]++,e[i]++,l[i]++,r[i]++;
			dfs1(s[i],l[i]);
			dfs2(e[i],r[i]);
			for(j=1;j<=n;j++)if(v1[j] && v2[j])break;
			if(j<=n)ans.pb(1);
			else ans.pb(0);
			memset(v1,0,sizeof(v1));
			memset(v2,0,sizeof(v2));
		}
		return ans;
	}
	for(i=1;i<=n;i++)
	{
		if(g[i].size()==1)
		{
			x=i;
			break;
		}
	}
	dfs(x,x);
	for(i=1;i<=q;i++)
	{
		s[i]=S[i-1],e[i]=E[i-1],l[i]=L[i-1],r[i]=R[i-1];
		s[i]++,e[i]++,l[i]++,r[i]++;
		s[i]=id[s[i]],e[i]=id[e[i]];
		vl[l[i]].pb(i);
		vr[r[i]].pb(i);
	}
	for(i=n;i>=1;i--)
	{
		upd(id[i]);
		for(j=0;j<vl[i].size();j++)
		{
			t=vl[i][j];
			if(s[t]<e[t])
			{
				st=s[t],dr=e[t],rs=-1;
				x=qry(s[t]-1);
				while(st<=dr)
				{
					mid=(st+dr)/2;
					if(qry(mid)-x==mid-s[t]+1)rs=mid,st=mid+1;
					else dr=mid-1;
				}
			}
			else
			{
				st=e[t],dr=s[t],rs=-1;
				x=qry(s[t]);
				while(st<=dr)
				{
					mid=(st+dr)/2;
					if(x-qry(mid-1)==s[t]-mid+1)rs=mid,dr=mid-1;
					else st=mid+1;
				}
			}
			lf[t]=rs;
		}
	}
	memset(bit,0,sizeof(bit));
	for(i=1;i<=n;i++)
	{
		upd(id[i]);
		for(j=0;j<vr[i].size();j++)
		{
			t=vr[i][j];
			if(s[t]<e[t])
			{
				st=s[t],dr=e[t],rs=-1;
				x=qry(e[t]);
				while(st<=dr)
				{
					mid=(st+dr)/2;
					if(x-qry(mid-1)==e[t]-mid+1)rs=mid,dr=mid-1;
					else st=mid+1;
				}
			}
			else
			{
				st=e[t],dr=s[t],rs=-1;
				x=qry(e[t]-1);
				while(st<=dr)
				{
					mid=(st+dr)/2;
					if(qry(mid)-x==mid-e[t]+1)rs=mid,st=mid+1;
					else dr=mid-1;
				}
			}
			rg[t]=rs;
		}
	}
	for(i=1;i<=q;i++)
	{
		if(s[i]<e[i])
		{
			if(lf[i]==-1 || rg[i]==-1 || lf[i]<rg[i])ans.pb(0);
			else ans.pb(1);
		}
		else
		{
			if(lf[i]==-1 || rg[i]==-1 || lf[i]>rg[i])ans.pb(0);
			else ans.pb(1);
		}
	}
	return ans;
}
/*int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>m>>q;
	while(m--)
	{
		cin>>x>>y;
		x++,y++;
		g[x].pb(y);
		g[y].pb(x);
	}
	for(i=1;i<=n;i++)
	{
		if(g[i].size()==1)
		{
			x=i;
			break;
		}
	}
	dfs(x,x);
	for(i=1;i<=q;i++)
	{
		cin>>s[i]>>e[i]>>l[i]>>r[i];
		s[i]++,e[i]++,l[i]++,r[i]++;
		s[i]=id[s[i]],e[i]=id[e[i]];
		vl[l[i]].pb(i);
		vr[r[i]].pb(i);
	}
	for(i=n;i>=1;i--)
	{
		upd(id[i]);
		for(j=0;j<vl[i].size();j++)
		{
			t=vl[i][j];
			if(s[t]<e[t])
			{
				st=s[t],dr=e[t],rs=-1;
				x=qry(s[t]-1);
				while(st<=dr)
				{
					mid=(st+dr)/2;
					if(qry(mid)-x==mid-s[t]+1)rs=mid,st=mid+1;
					else dr=mid-1;
				}
			}
			else
			{
				st=e[t],dr=s[t],rs=-1;
				x=qry(s[t]);
				while(st<=dr)
				{
					mid=(st+dr)/2;
					if(x-qry(mid-1)==s[t]-mid+1)rs=mid,dr=mid-1;
					else st=mid+1;
				}
			}
			lf[t]=rs;
		}
	}
	memset(bit,0,sizeof(bit));
	for(i=1;i<=n;i++)
	{
		upd(id[i]);
		for(j=0;j<vr[i].size();j++)
		{
			t=vr[i][j];
			if(s[t]<e[t])
			{
				st=s[t],dr=e[t],rs=-1;
				x=qry(e[t]);
				while(st<=dr)
				{
					mid=(st+dr)/2;
					if(x-qry(mid-1)==e[t]-mid+1)rs=mid,dr=mid-1;
					else st=mid+1;
				}
			}
			else
			{
				st=e[t],dr=s[t],rs=-1;
				x=qry(e[t]-1);
				while(st<=dr)
				{
					mid=(st+dr)/2;
					if(qry(mid)-x==mid-e[t]+1)rs=mid,st=mid+1;
					else dr=mid-1;
				}
			}
			rg[t]=rs;
		}
	}
	for(i=1;i<=q;i++)
	{
		if(s[i]<e[i])
		{
			if(lf[i]==-1 || rg[i]==-1 || lf[i]<rg[i])cout<<0<<" ";
			else cout<<1<<" ";
		}
		else
		{
			if(lf[i]==-1 || rg[i]==-1 || lf[i]>rg[i])cout<<0<<" ";
			else cout<<1<<" ";
		}
		cout<<lf[i]<<" "<<rg[i]<<endl;
	}
	cout<<endl;
    return 0;
}
/*
8 7 1
0 2
2 4
4 1
1 6
6 5
5 3
3 7
4 7 3 7
*/

Compilation message (stderr)

werewolf.cpp:282:1: warning: "/*" within comment [-Wcomment]
 /*
  
werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[x].size();i++)
              ~^~~~~~~~~~~~
werewolf.cpp: In function 'void dfs1(int, int)':
werewolf.cpp:43:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[x].size();i++)if(g[x][i]>=cmp && !v1[g[x][i]])dfs1(g[x][i],cmp);
              ~^~~~~~~~~~~~
werewolf.cpp: In function 'void dfs2(int, int)':
werewolf.cpp:48:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[x].size();i++)if(g[x][i]<=cmp && !v2[g[x][i]])dfs2(g[x][i],cmp);
              ~^~~~~~~~~~~~
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:97:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<vl[i].size();j++)
           ~^~~~~~~~~~~~~
werewolf.cpp:129:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<vr[i].size();j++)
           ~^~~~~~~~~~~~~

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