Submission #697724

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

bitaro

#include "bits/stdc++.h"
#pragma GCC optimize ("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
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 = 500;
bool forbidden[MAXN], cnt[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});
				}
			}
 
       // bool cnt[i+5];
        //vector< vector<int> > vals(i+5);
        vector<int> clean;
        for(int a = 0; a < big[i].size(); a++)
        {
            vals[big[i][a].first].push_back(big[i][a].second);
            clean.push_back(big[i][a].first);

        }
        //for(int a = 0; a <= i; a++)
            //cnt[a] = false;
		//sort(big[i].begin(), big[i].end());
		//reverse(big[i].begin(), big[i].end());
		//vector< pair<int, int > > temp;
        big[i].clear();
        for(int a = i; a >= 0; a--)
        {
            cnt[a] = false;
            if(big[i].size() >= sqrtval)
                continue;
            for(int p : vals[a])
            {
                if(cnt[p])
                    continue;
                big[i].push_back({a, p});
                cnt[p] = true;
            }
        }
		
        for(int num : clean)
            vals[num].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:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      | 
bitaro.cpp: In function 'int main()':
bitaro.cpp:50:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int a = 0; a < big[i].size(); a++)
      |                        ~~^~~~~~~~~~~~~~~
bitaro.cpp:98:7: warning: unused variable 'curridx' [-Wunused-variable]
   98 |   int curridx = 0;
      |       ^~~~~~~

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