Submission #697531

#	Time	Username	Problem	Language	Result	Execution time	Memory
697531		speedyArda	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2077 ms	409768 KiB

bitaro

#include "bits/stdc++.h"

using namespace std;
const int MAXN = 1e5+5;



vector< vector< int> > rev(MAXN);
vector< vector< pair<int, int>  > > big(MAXN);
int sqrtval;



int main() 
{
	int n, m, q;
	cin >> n >> m >> q;
	sqrtval = sqrt(n);
	for(int i = 1; i <= m; i++)
	{
		int f, s;
		cin >> f >> s;
		rev[s].push_back(f);
	}


	for(int i = 1; i <= n; i++)
	{
		big[i].push_back({0, i});

			for(int e : rev[i])
			{
				for(pair<int, int> val : big[e])
				{
					big[i].push_back({val.first + 1, val.second});
				}
			}


		sort(big[i].begin(), big[i].end());
		reverse(big[i].begin(), big[i].end());
		vector< pair<int, int > > temp;
		for(int l = 0; l < big[i].size(); l++)
		{
			if(temp.empty() || temp.back().second != big[i][l].second)
				temp.push_back(big[i][l]);
		}
		big[i] = temp;
		if(big[i].size() > sqrtval)
		big[i].resize(sqrtval);
		
		
		
	}



	while(q--)
	{
		int city, forbiddencnt;
		cin >> city >> forbiddencnt;
		set<int> forbidden;
		int ans = -1;
		for(int i = 1; i <= forbiddencnt; i++)
		{
			int f;
			cin >> f;
			forbidden.insert(f);
			//if()
		}
		//cout << city << " " << forbiddencnt << " " << sqrtval << "\n";
		if(forbiddencnt >= sqrtval)
		{
			//cout << "g\n";
			int dp[n+5];
			for(int i = 0; i <= n; i++)
			{
				dp[i] = -1e9;
			}

			dp[city] = 0;
			for(int i = city; i >= 1; i--)
			{
				//cout << dp[i] << "\n";
				if(forbidden.find(i) == forbidden.end())
					ans = max(ans, dp[i]);
				for(int e : rev[i])
				{
					dp[e] = max(dp[e], dp[i] + 1);
				}
			}


		} else 
		{
			for(int i = 0; i < min((int)big[city].size(), sqrtval); i++)
			{
				//cout << i << "\n";
				if(forbidden.find(big[city][i].second) == forbidden.end())
				{
					//cout << "G: " << big[city][i].second << "\n";
					ans = big[city][i].first;
					break;
				}
			}			
		}

		cout << ans << "\n";
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(int l = 0; l < big[i].size(); l++)
      |                  ~~^~~~~~~~~~~~~~~
bitaro.cpp:49:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |   if(big[i].size() > sqrtval)
      |      ~~~~~~~~~~~~~~^~~~~~~~~

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