oj.uz

Submission #100375

# Submission time Handle Problem Language Result Execution time Memory
100375 2019-03-10T16:37:41 Z MvC Werewolf (IOI18_werewolf) C++11
49 / 100
 764 ms 52596 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+50;
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 18 ms 14464 KB Output is correct
2 Correct 17 ms 14464 KB Output is correct
3 Correct 17 ms 14464 KB Output is correct
4 Correct 18 ms 14464 KB Output is correct
5 Correct 16 ms 14464 KB Output is correct
6 Correct 16 ms 14464 KB Output is correct
7 Correct 16 ms 14464 KB Output is correct
8 Correct 16 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 18 ms 14464 KB Output is correct
2 Correct 17 ms 14464 KB Output is correct
3 Correct 17 ms 14464 KB Output is correct
4 Correct 18 ms 14464 KB Output is correct
5 Correct 16 ms 14464 KB Output is correct
6 Correct 16 ms 14464 KB Output is correct
7 Correct 16 ms 14464 KB Output is correct
8 Correct 16 ms 14464 KB Output is correct
9 Correct 17 ms 14464 KB Output is correct
10 Correct 260 ms 14928 KB Output is correct
11 Correct 205 ms 14976 KB Output is correct
12 Correct 42 ms 15100 KB Output is correct
13 Correct 370 ms 14848 KB Output is correct
14 Correct 213 ms 14968 KB Output is correct
15 Correct 282 ms 15148 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 753 ms 49748 KB Output is correct
2 Correct 688 ms 49824 KB Output is correct
3 Correct 653 ms 49652 KB Output is correct
4 Correct 714 ms 49840 KB Output is correct
5 Correct 764 ms 49744 KB Output is correct
6 Correct 751 ms 49716 KB Output is correct
7 Correct 680 ms 47648 KB Output is correct
8 Correct 725 ms 49908 KB Output is correct
9 Correct 522 ms 48748 KB Output is correct
10 Correct 559 ms 48600 KB Output is correct
11 Correct 604 ms 48628 KB Output is correct
12 Correct 635 ms 49488 KB Output is correct
13 Correct 714 ms 49744 KB Output is correct
14 Correct 715 ms 49908 KB Output is correct
15 Correct 692 ms 49780 KB Output is correct
16 Correct 702 ms 49780 KB Output is correct
17 Correct 687 ms 47704 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14464 KB Output is correct
2 Correct 17 ms 14464 KB Output is correct
3 Correct 17 ms 14464 KB Output is correct
4 Correct 18 ms 14464 KB Output is correct
5 Correct 16 ms 14464 KB Output is correct
6 Correct 16 ms 14464 KB Output is correct
7 Correct 16 ms 14464 KB Output is correct
8 Correct 16 ms 14464 KB Output is correct
9 Correct 17 ms 14464 KB Output is correct
10 Correct 260 ms 14928 KB Output is correct
11 Correct 205 ms 14976 KB Output is correct
12 Correct 42 ms 15100 KB Output is correct
13 Correct 370 ms 14848 KB Output is correct
14 Correct 213 ms 14968 KB Output is correct
15 Correct 282 ms 15148 KB Output is correct
16 Correct 753 ms 49748 KB Output is correct
17 Correct 688 ms 49824 KB Output is correct
18 Correct 653 ms 49652 KB Output is correct
19 Correct 714 ms 49840 KB Output is correct
20 Correct 764 ms 49744 KB Output is correct
21 Correct 751 ms 49716 KB Output is correct
22 Correct 680 ms 47648 KB Output is correct
23 Correct 725 ms 49908 KB Output is correct
24 Correct 522 ms 48748 KB Output is correct
25 Correct 559 ms 48600 KB Output is correct
26 Correct 604 ms 48628 KB Output is correct
27 Correct 635 ms 49488 KB Output is correct
28 Correct 714 ms 49744 KB Output is correct
29 Correct 715 ms 49908 KB Output is correct
30 Correct 692 ms 49780 KB Output is correct
31 Correct 702 ms 49780 KB Output is correct
32 Correct 687 ms 47704 KB Output is correct
33 Incorrect 559 ms 52596 KB Output isn't correct
34 Halted 0 ms 0 KB -