Submission #743241

#	Time	Username	Problem	Language	Result	Execution time	Memory
743241		Azther0z	Bitaro’s Party (JOI18_bitaro)	C++11	100 / 100	1271 ms	215080 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
const int B=150;
vector<vector<int>> adjl(100001);
vector<vector<pair<int,int>>> far(100001);
vector<int> visited(100001,0),val(100001,0);
bitset<100001> busy;
bool cmp(int x,int y)
{
	return val[x]>val[y];
}
int main()
{
	int n,m,q;
	scanf("%d%d%d",&n,&m,&q);
	while(m--)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		adjl[b].push_back(a);
	}
	for(int i=1;i<=n;i++)
	{
		vector<int> all;
		for(auto j:adjl[i])
		{
			for(auto f:far[j])
			{
				if(visited[f.second]!=i)
				{
					visited[f.second]=i;
					all.push_back(f.second);
					val[f.second]=f.first+1;
				}
				else
				{
					val[f.second]=max(val[f.second],f.first+1);
				}
			}
			if(visited[j]!=i)
			{
				visited[j]=i;
				all.push_back(j);
				val[j]=1;
			}
		}
		all.push_back(i);
		sort(all.begin(),all.end(),cmp);
		for(int j=0;j<min((int)all.size(),B);j++)
			far[i].push_back({val[all[j]],all[j]});
	}
	while(q--)
	{
		busy=0;
		int a,b,c;
		scanf("%d%d",&a,&b);
		for(int i=0;i<b;i++)
		{
			scanf("%d",&c);
			busy[c]=true;
		}
		if(b>=B)
		{
			vector<int> dp(n+1,-1);
			for(int i=1;i<=a;i++)
			{
				if(!busy[i]) dp[i]=max(dp[i],0);
				for(auto next:adjl[i])
					if(dp[next]!=-1)
						dp[i]=max(dp[i],dp[next]+1);
			}
			printf("%d\n",dp[a]);
		}
		else
		{
			bool check=false;
			for(auto f:far[a])
			{
				if(!busy[f.second])
				{
					printf("%d\n",f.first);
					check=true;
					break;
				}
			}
			if(!check) printf("-1\n");
		}
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%d%d%d",&n,&m,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:59:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |    scanf("%d",&c);
      |    ~~~~~^~~~~~~~~

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