Submission #99240

#	Time	Username	Problem	Language	Result	Execution time	Memory
99240		TadijaSebez	Bitaro’s Party (JOI18_bitaro)	C++11	100 / 100	1006 ms	259196 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=100050;
const int inf=1e9+7;
const int S=317;
vector<int> E[N];
int a[N][S][2],sz[N],tmp[S][2],has[N],dp[N];
void Merge(int x, int y)
{
	int tsz=0,i=0,j=0;
	while(i<sz[x] && j<sz[y] && tsz<S)
	{
		if(has[a[x][i][0]]) i++;
		else if(has[a[y][j][0]]) j++;
		else if(a[x][i][1]>a[y][j][1]+1)
		{
			tmp[tsz][0]=a[x][i][0];
			tmp[tsz][1]=a[x][i][1];
			has[tmp[tsz][0]]=1;tsz++;i++;
		}
		else
		{
			tmp[tsz][0]=a[y][j][0];
			tmp[tsz][1]=a[y][j][1]+1;
			has[tmp[tsz][0]]=1;tsz++;j++;
		}
	}
	while(i<sz[x] && tsz<S)
	{
		if(has[a[x][i][0]]) i++;
		else
		{
			tmp[tsz][0]=a[x][i][0];
			tmp[tsz][1]=a[x][i][1];
			has[tmp[tsz][0]]=1;tsz++;i++;
		}
	}
	while(j<sz[y] && tsz<S)
	{
		if(has[a[y][i][0]]) j++;
		else
		{
			tmp[tsz][0]=a[y][j][0];
			tmp[tsz][1]=a[y][j][1]+1;
			has[tmp[tsz][0]]=1;tsz++;j++;
		}
	}
	for(i=0;i<tsz;i++)
	{
		a[x][i][0]=tmp[i][0];
		a[x][i][1]=tmp[i][1];
		has[tmp[i][0]]=0;
	}
	sz[x]=tsz;
}
int main()
{
	int n,m,q,u,v,i;
	scanf("%i %i %i",&n,&m,&q);
	for(i=1;i<=m;i++) scanf("%i %i",&u,&v),E[v].pb(u);
	for(i=1;i<=n;i++)
	{
		a[i][0][0]=i;
		a[i][0][1]=0;
		sz[i]=1;
		for(int j:E[i]) Merge(i,j);
	}
	for(i=1;i<=q;i++)
	{
		int t,y;
		scanf("%i %i",&t,&y);
		vector<int> bad(y);
		for(int &j:bad) scanf("%i",&j),has[j]=1;
		if(y>=S)
		{
			for(int j=1;j<=t;j++)
			{
				if(has[j]) dp[j]=-inf;
				else dp[j]=0;
				for(int k:E[j]) dp[j]=max(dp[j],dp[k]+1);
			}
			if(dp[t]<0) dp[t]=-1;
			printf("%i\n",dp[t]);
		}
		else
		{
			int ans=-1;
			for(int j=0;j<sz[t];j++) if(!has[a[t][j][0]])
			{
				ans=a[t][j][1];
				break;
			}
			printf("%i\n",ans);
		}
		for(int j:bad) has[j]=0;
	}
	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&m,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:61:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<=m;i++) scanf("%i %i",&u,&v),E[v].pb(u);
                    ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
bitaro.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&t,&y);
   ~~~~~^~~~~~~~~~~~~~~
bitaro.cpp:74:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int &j:bad) scanf("%i",&j),has[j]=1;
                   ~~~~~~~~~~~~~~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86