oj.uz

Submission #100376

# Submission time Handle Problem Language Result Execution time Memory
100376 2019-03-10T16:51:39 Z MvC Werewolf (IOI18_werewolf) C++11
49 / 100
 790 ms 49944 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14464 KB Output is correct
2 Correct 15 ms 14592 KB Output is correct
3 Correct 16 ms 14464 KB Output is correct
4 Correct 16 ms 14464 KB Output is correct
5 Correct 15 ms 14464 KB Output is correct
6 Correct 15 ms 14464 KB Output is correct
7 Correct 16 ms 14464 KB Output is correct
8 Correct 17 ms 14464 KB Output is correct
9 Correct 17 ms 14464 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14464 KB Output is correct
2 Correct 15 ms 14592 KB Output is correct
3 Correct 16 ms 14464 KB Output is correct
4 Correct 16 ms 14464 KB Output is correct
5 Correct 15 ms 14464 KB Output is correct
6 Correct 15 ms 14464 KB Output is correct
7 Correct 16 ms 14464 KB Output is correct
8 Correct 17 ms 14464 KB Output is correct
9 Correct 17 ms 14464 KB Output is correct
10 Correct 268 ms 14968 KB Output is correct
11 Correct 173 ms 14840 KB Output is correct
12 Correct 40 ms 14840 KB Output is correct
13 Correct 321 ms 14840 KB Output is correct
14 Correct 210 ms 14764 KB Output is correct
15 Correct 270 ms 14968 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 684 ms 49820 KB Output is correct
2 Correct 752 ms 49780 KB Output is correct
3 Correct 717 ms 49712 KB Output is correct
4 Correct 664 ms 49792 KB Output is correct
5 Correct 670 ms 49908 KB Output is correct
6 Correct 777 ms 49804 KB Output is correct
7 Correct 626 ms 47600 KB Output is correct
8 Correct 625 ms 49756 KB Output is correct
9 Correct 651 ms 48748 KB Output is correct
10 Correct 554 ms 48372 KB Output is correct
11 Correct 598 ms 48756 KB Output is correct
12 Correct 571 ms 49516 KB Output is correct
13 Correct 692 ms 49800 KB Output is correct
14 Correct 728 ms 49944 KB Output is correct
15 Correct 703 ms 49780 KB Output is correct
16 Correct 790 ms 49880 KB Output is correct
17 Correct 648 ms 47600 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14464 KB Output is correct
2 Correct 15 ms 14592 KB Output is correct
3 Correct 16 ms 14464 KB Output is correct
4 Correct 16 ms 14464 KB Output is correct
5 Correct 15 ms 14464 KB Output is correct
6 Correct 15 ms 14464 KB Output is correct
7 Correct 16 ms 14464 KB Output is correct
8 Correct 17 ms 14464 KB Output is correct
9 Correct 17 ms 14464 KB Output is correct
10 Correct 268 ms 14968 KB Output is correct
11 Correct 173 ms 14840 KB Output is correct
12 Correct 40 ms 14840 KB Output is correct
13 Correct 321 ms 14840 KB Output is correct
14 Correct 210 ms 14764 KB Output is correct
15 Correct 270 ms 14968 KB Output is correct
16 Correct 684 ms 49820 KB Output is correct
17 Correct 752 ms 49780 KB Output is correct
18 Correct 717 ms 49712 KB Output is correct
19 Correct 664 ms 49792 KB Output is correct
20 Correct 670 ms 49908 KB Output is correct
21 Correct 777 ms 49804 KB Output is correct
22 Correct 626 ms 47600 KB Output is correct
23 Correct 625 ms 49756 KB Output is correct
24 Correct 651 ms 48748 KB Output is correct
25 Correct 554 ms 48372 KB Output is correct
26 Correct 598 ms 48756 KB Output is correct
27 Correct 571 ms 49516 KB Output is correct
28 Correct 692 ms 49800 KB Output is correct
29 Correct 728 ms 49944 KB Output is correct
30 Correct 703 ms 49780 KB Output is correct
31 Correct 790 ms 49880 KB Output is correct
32 Correct 648 ms 47600 KB Output is correct
33 Incorrect 500 ms 44012 KB Output isn't correct
34 Halted 0 ms 0 KB -