Submission #998986

#	Time	Username	Problem	Language	Result	Execution time	Memory
998986		envifly	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	758 ms	143388 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
	cin.tie(0) -> sync_with_stdio(0);
	int n, m, q;
	cin >> n >> m >> q;
	vector<vector<int>> rg(n);
	for(int i = 0; i < m; i++){
		int u, v; 
		cin >> u >> v;
		rg[--v].push_back(--u);
	}
	
	int SQ = 100; // cutoff for sqrt decomp
	vector<vector<pair<int, int>>> path_sizes(n); // stores the 100 longest paths ending at i
	vector<int> from(n, -1); // longest path starting at that node
	
	for(int i = 0; i < n; i++){
		path_sizes[i].push_back({0, i});
		vector<int> from_indicies;
		
		for(int j: rg[i]){
			for(auto [dist, idx]: path_sizes[j]){
				if(from[idx] == -1){
					// if we haven't gotten a path from this index yet
					from_indicies.push_back(idx);
					from[idx] = dist + 1;
				}
				else{
					// take max with already processed dist
					from[idx] = max(from[idx], dist + 1);
				}
			}
		}
		
		for(int j: from_indicies){
			path_sizes[i].push_back({from[j], j});
		}
		sort(path_sizes[i].rbegin(), path_sizes[i].rend());
		// pop until sqrt paths
		while(path_sizes[i].size() > SQ){
			path_sizes[i].pop_back();
		}
		
		// reset 
		for(int j: from_indicies){
			from[j] = -1;
		}
	}
	
	vector<bool> blocked(n);
	while(q--){
		int t, y;
		cin >> t >> y;
		--t;
		
		vector<int> c(y);
		for(int i = 0; i < y; i++){
			cin >> c[i];
			--c[i];
			blocked[c[i]] = true;
		}
		
		int ans = -1;
		if(y >= SQ){
			// brute force dp since number of queries is bounded by sqrt
			vector<int> dp(t + 1, -1); // dp[i] stores longest path ending at i
			dp[t] = 0;
			for(int i = t; i >= 0; i--){
				if(dp[i] == -1){
					continue;
				}
				if(!blocked[i]){
					ans = max(ans, dp[i]);
				}
				for(int j: rg[i]){
					dp[j] = max(dp[j], dp[i] + 1);
				}
			}
		}
		else{
			for(auto [dist, idx] : path_sizes[t]){
				if(!blocked[idx]){
					ans = dist;
					break;
				}
			}
		}
		
		cout << ans << "\n";
		
		for(int i: c){
			blocked[i] = false;
		}
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:43:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |   while(path_sizes[i].size() > SQ){
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~

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