oj.uz

Submission #100377

# Submission time Handle Problem Language Result Execution time Memory
100377 2019-03-10T16:56:13 Z MvC Werewolf (IOI18_werewolf) C++11
49 / 100
 940 ms 56564 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;
ll 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<ll>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 14720 KB Output is correct
2 Correct 16 ms 14592 KB Output is correct
3 Correct 16 ms 14592 KB Output is correct
4 Correct 15 ms 14464 KB Output is correct
5 Correct 17 ms 14464 KB Output is correct
6 Correct 16 ms 14592 KB Output is correct
7 Correct 16 ms 14592 KB Output is correct
8 Correct 18 ms 14592 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 14720 KB Output is correct
2 Correct 16 ms 14592 KB Output is correct
3 Correct 16 ms 14592 KB Output is correct
4 Correct 15 ms 14464 KB Output is correct
5 Correct 17 ms 14464 KB Output is correct
6 Correct 16 ms 14592 KB Output is correct
7 Correct 16 ms 14592 KB Output is correct
8 Correct 18 ms 14592 KB Output is correct
9 Correct 17 ms 14464 KB Output is correct
10 Correct 326 ms 14988 KB Output is correct
11 Correct 195 ms 14840 KB Output is correct
12 Correct 41 ms 14940 KB Output is correct
13 Correct 335 ms 15072 KB Output is correct
14 Correct 228 ms 14980 KB Output is correct
15 Correct 337 ms 15096 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 940 ms 56464 KB Output is correct
2 Correct 682 ms 56436 KB Output is correct
3 Correct 705 ms 56308 KB Output is correct
4 Correct 748 ms 56552 KB Output is correct
5 Correct 764 ms 56512 KB Output is correct
6 Correct 744 ms 56436 KB Output is correct
7 Correct 609 ms 54212 KB Output is correct
8 Correct 629 ms 56308 KB Output is correct
9 Correct 493 ms 55380 KB Output is correct
10 Correct 550 ms 55064 KB Output is correct
11 Correct 550 ms 55664 KB Output is correct
12 Correct 620 ms 56048 KB Output is correct
13 Correct 780 ms 56460 KB Output is correct
14 Correct 753 ms 56436 KB Output is correct
15 Correct 760 ms 56436 KB Output is correct
16 Correct 727 ms 56564 KB Output is correct
17 Correct 665 ms 54292 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14720 KB Output is correct
2 Correct 16 ms 14592 KB Output is correct
3 Correct 16 ms 14592 KB Output is correct
4 Correct 15 ms 14464 KB Output is correct
5 Correct 17 ms 14464 KB Output is correct
6 Correct 16 ms 14592 KB Output is correct
7 Correct 16 ms 14592 KB Output is correct
8 Correct 18 ms 14592 KB Output is correct
9 Correct 17 ms 14464 KB Output is correct
10 Correct 326 ms 14988 KB Output is correct
11 Correct 195 ms 14840 KB Output is correct
12 Correct 41 ms 14940 KB Output is correct
13 Correct 335 ms 15072 KB Output is correct
14 Correct 228 ms 14980 KB Output is correct
15 Correct 337 ms 15096 KB Output is correct
16 Correct 940 ms 56464 KB Output is correct
17 Correct 682 ms 56436 KB Output is correct
18 Correct 705 ms 56308 KB Output is correct
19 Correct 748 ms 56552 KB Output is correct
20 Correct 764 ms 56512 KB Output is correct
21 Correct 744 ms 56436 KB Output is correct
22 Correct 609 ms 54212 KB Output is correct
23 Correct 629 ms 56308 KB Output is correct
24 Correct 493 ms 55380 KB Output is correct
25 Correct 550 ms 55064 KB Output is correct
26 Correct 550 ms 55664 KB Output is correct
27 Correct 620 ms 56048 KB Output is correct
28 Correct 780 ms 56460 KB Output is correct
29 Correct 753 ms 56436 KB Output is correct
30 Correct 760 ms 56436 KB Output is correct
31 Correct 727 ms 56564 KB Output is correct
32 Correct 665 ms 54292 KB Output is correct
33 Incorrect 548 ms 52468 KB Output isn't correct
34 Halted 0 ms 0 KB -