Submission #1091068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091068		MrNanama	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2044 ms	514188 KiB

bitaro

#include <bits/stdc++.h>
#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;


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}));

	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});

		vector<ll> dist(n, -1);
		dist[i] = 0;

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

		vector<pair<ll,ll>> dist2(n);

		for(ll j=0; j<n; j++){
			dist2[j] = {dist[j], j};
		}

		sort(dist2.begin(), dist2.end(), greater<pair<ll,ll>>());

		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){
			dp[i][curr] = pq.top();
			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;
	}
	*/


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

		set<ll> banned;

		for(ll j=0; j<qnt; j++){
			ll c;
			cin >> c;
			c--;
			banned.insert(c);
		}

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

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

			vector<ll> dist(n, -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(banned.count(i) == 0){ans = max<ll>(ans, dist[i]);}
			}

			cout << ans << endl;

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

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

}

int main(){

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

	solve();
}

Compilation message (stderr)

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

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