제출 #697560

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
697560		speedyArda	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2092 ms	405204 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 = 500;
bool forbidden[MAXN];


int main() 
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	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++)
	{
		//set< pair<int, int> temp;
		//temp.push_back(temp);
		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;
		vector<int> forbiddencurr;
		int ans = -1;
		for(int i = 1; i <= forbiddencnt; i++)
		{
			int f;
			cin >> f;
			forbiddencurr.push_back(f);
			forbidden[f] = true;
			//if()
		}
		int curridx = 0;
		//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[i])
					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[big[city][i].second])
				{
					//cout << "G: " << big[city][i].second << "\n";
					ans = big[city][i].first;
					break;
				}
			}			
		}
		for(int e : forbiddencurr)
			forbidden[e] = false;
		cout << ans << "\n";
	}
}

컴파일 시 표준 에러 (stderr) 메시지

bitaro.cpp: In function 'int main()':
bitaro.cpp:47: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]
   47 |   for(int l = 0; l < big[i].size(); l++)
      |                  ~~^~~~~~~~~~~~~~~
bitaro.cpp:53: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]
   53 |   if(big[i].size() > sqrtval)
      |      ~~~~~~~~~~~~~~^~~~~~~~~
bitaro.cpp:76:7: warning: unused variable 'curridx' [-Wunused-variable]
   76 |   int curridx = 0;
      |       ^~~~~~~

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