Submission #698435

#	Time	Username	Problem	Language	Result	Execution time	Memory
698435		speedyArda	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1476 ms	110820 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);
//vector< vector<int> > vals(MAXN);
const int sqrtval = 100;
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++)
	//	sort(rev[i].begin(), rev[i].end());
 
	vector<pair<int, int> > temp;

	for(int i = 1; i <= n; i++)
	{
        //vector<int> clean;
		
		temp.push_back({0, i});
 
			for(int e : rev[i])
			{
				for(pair<int, int> val : big[e])
				{
					temp.push_back({val.first + 1, val.second});
				}
			}
 

		sort(temp.begin(), temp.end());
        
        for(int l = temp.size() - 1; l >= 0; l--)
        {
            if(big[i].size() >= sqrtval)
                break;
            if(forbidden[temp[l].second])
                continue;
            big[i].push_back(temp[l]);
            forbidden[temp[l].second] = true;
            //clean.push_back(big[i][l].second);
        }
		
        for(pair<int, int> num : big[i])
            forbidden[num.second] = false;
		temp.clear();
		
	}
 
 
 
	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 <= city; 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";
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:82:7: warning: unused variable 'curridx' [-Wunused-variable]
   82 |   int curridx = 0;
      |       ^~~~~~~

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