Submission #1091076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091076		MrNanama	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	995 ms	173904 KiB

bitaro

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define pb push_back
#define fi first
#define se second

using namespace std;
using ll = long long;

template <typename T> ostream& operator<<(ostream& os, const vector<T>& vec){for (auto itr : vec){os << itr << " ";} return os;}

ll n,m,q,block;
vector<vector<ll>> neigh;
vector<vector<pair<ll,ll>>> dp;
vector<ll> visited;


/*
pair<ll,ll> dfs(ll v, set<ll>& banned){
	ll max_val = -1;
	ll max_node = -1;

	for(ll go:neigh[v]){
		pair<ll,ll> p = dfs(go, banned);

		if(max_val <= p.fi+1 && p.se != -1){
			max_val = p.fi+1;
			max_node = p.se;
		}
	}

	if(banned.count(v) == 0){
		if(max_val <= 0){
			max_val = 0;
			max_node = v;
		}
	}

	return {max_val, max_node};
}
*/

void solve(){

	cin >> n >> m >> q;
	block = ceil(sqrt(n))+2;
	block = 100;

	neigh.resize(n);
	dp.assign(n, vector<pair<ll,ll>>(block, {-1,-1}));
	visited.assign(n, -1);

	for(ll i=0; i<m; i++){
		ll n1,n2;
		cin >> n1 >> n2;
		n1--; n2--;

		if(n1 < n2){swap(n1,n2);}

		neigh[n1].pb(n2);
	}

	for(ll i=0; i<n; i++){

		priority_queue<pair<ll,ll>> pq;
		pq.push({0,i});

		for(ll go:neigh[i]){
			for(pair<ll,ll> p:dp[go]){
				//make sure break doesnt break
				if(p.se == -1){break;}
				
				pq.push({p.fi+1, p.se});
			}
		}

		
		/*
		for(ll j=0; j<min<ll>(n,block); j++){
			dp[i][j] = {dist2[j].fi, dist2[j].se};
		}
		*/

		ll curr = 0;
		while(!pq.empty() && curr < block){
			pair<ll,ll> c = pq.top();
			if(visited[c.se] == i){pq.pop(); continue;}

			dp[i][curr] = {c.fi, c.se};
			visited[c.se] = i;
			pq.pop();
			curr++;
		}
	}

	/*
	for(ll i=0; i<n; i++){
		cout << i << ": ";
		for(ll j=0; j<block; j++){
			cout << dp[i][j].fi << " ";
		}
		cout << endl;
	}
	*/


	vector<ll> dist(n, -1);
	stack<ll> banned_list;
	vector<ll> is_banned(n,0);


	for(ll i=0; i<q; i++){
		ll n1, qnt;
		cin >> n1 >> qnt;
		n1--;

		for(ll j=0; j<qnt; j++){
			ll c;
			cin >> c;
			c--;
			banned_list.push(c);
			is_banned[c] = 1;
		}

		if(banned_list.size() <= block-2){

			for(ll j=0; j<block; j++){
				if(is_banned[dp[n1][j].se] == 1){
					continue;
				}else{
					cout << dp[n1][j].fi << endl;
					break;
				}
			}
		}else{

			fill(dist.begin(), dist.end(), -1);			

			dist[n1] = 0;

			for(ll i=n1; i>=0; i--){
				if(dist[i] == -1){continue;}

				for(ll go:neigh[i]){
					dist[go] = max<ll>(dist[go], dist[i]+1); 
				}
			}

			ll ans = -1;
			for(ll i=0; i<n; i++){
				if(is_banned[i] == 0){ans = max<ll>(ans, dist[i]);}
			}

			cout << ans << endl;

			/*
			pair<ll,ll> p = dfs(n1,banned);

			cout << p.fi << endl;
			*/
		}

		while(banned_list.size() > 0){
			ll c = banned_list.top();
			is_banned[c] = 0;

			banned_list.pop();
		}
	}

}

int main(){

	ios_base::sync_with_stdio(false); cin.tie(NULL);

	solve();
}

Compilation message (stderr)

bitaro.cpp: In function 'void solve()':
bitaro.cpp:125:25: warning: comparison of integer expressions of different signedness: 'std::stack<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  125 |   if(banned_list.size() <= block-2){
      |      ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

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