Submission #1081856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081856		Thunnus	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	609 ms	286408 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size() 

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	const int SZ = 100;
	int n, m, q, a, b;
	cin >> n >> m >> q;
	vvi adj(n), radj(n);
	for(int i = 0; i < m; i++){
		cin >> a >> b;
		adj[--a].emplace_back(--b);
		radj[b].emplace_back(a);
	}

	vector<vector<pii>> bestSZ(n);
	vi starting(n, -1);
	for(int v = 0; v < n; v++){ // Duplicates are the issue
		vi from;
		bestSZ[v].emplace_back(0, v);
		for(int &u : radj[v]){
			for(pii &d : bestSZ[u]){
				if(starting[d.se] == -1){
					from.emplace_back(d.se);
					starting[d.se] = d.fi + 1;
				}
				else{
					starting[d.se] = max(starting[d.se], d.fi + 1);
				}
			}
		}
		for(int &u : from){
			bestSZ[v].emplace_back(starting[u], u);
		}
		sort(bestSZ[v].begin(), bestSZ[v].end(), greater<pii>());
		while(sz(bestSZ[v]) > SZ){
			bestSZ[v].pop_back();
		}

		for(int &u : from){
			starting[u] = -1;
		}
	}

	vb can(n, true);
	while(q--){
		int t, y, ans = -1;
		cin >> t >> y;
		t--;
		vi yi(y);
		for(int i = 0; i < y; i++){
			cin >> yi[i];
			can[--yi[i]] = false;
		}

		if(y >= SZ){
			vi dp(t + 1, -1);
			dp[t] = 0;
			for(int v = t; v >= 0; v--){
				if(dp[v] == -1) continue;
				if(can[v]) ans = max(ans, dp[v]);
				for(int &u : radj[v]){
					dp[u] = max(dp[u], dp[v] + 1);
				}
			}
		}
		else{
			for(pii &p : bestSZ[t]){
				if(can[p.se]){
					ans = p.fi;
					break;
				}
			}
		}
		
		for(int i = 0; i < y; i++){
			can[yi[i]] = true;
		}
		cout << ans << "\n";
	}
	return 0;
}

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