Submission #457868

#	Time	Username	Problem	Language	Result	Execution time	Memory
457868		zeyu	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2089 ms	126032 KiB

bitaro

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
const int B = 320;
int n, m, q;
typedef pair<int, int> pi;
vector<int> prv[maxn];
vector<pi> far[maxn];
vector<int> vis(maxn, -1), val(maxn);
vector<int> y(maxn, -1);

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> q;
	for (int i = 0; i < m; i ++){
		int x, y;
		cin >> x >> y;
		x --; y --;
		prv[y].push_back(x);
	}
	for (int i = 0; i < n; i ++){
		vector<int> all;
		for (int j = 0; j < (int)prv[i].size(); j ++){
			int x = prv[i][j];
			for (int k = 0; k < far[x].size(); k ++){
				int z = far[x][k].second;
				if (vis[z] != i){
					vis[z] = i;
					all.push_back(z);
					val[z] = far[x][k].first + 1;
				} else{
					val[z] = max(val[z], far[x][k].first + 1);
				}
			}
			if (vis[x] != i){
				vis[x] = i;
				all.push_back(x);
				val[x] = 1;
			}
		}
		set<pi> dist;
		dist.insert(make_pair(0, i));
		for (int j = 0; j < all.size(); j ++){
			if (dist.size() < B) dist.insert(make_pair(val[all[j]], all[j]));
			else{
				if (val[all[j]] > dist.begin() -> first){
					dist.erase(dist.begin());
					dist.insert(make_pair(val[all[j]], all[j]));
				}
			}
		}
		for (set<pi>::reverse_iterator j = dist.rbegin(); j != dist.rend(); j ++){
			far[i].push_back(*j);
		}
	}
	while(q --){
		int t; cin >> t; t --;
		int r; cin >> r;
		for (int i = 0; i < r; i ++){
			int p; cin >> p; y[p - 1] = q;
		}
		if (r >= B){
			vector<int> dp(n, -1);
			for (int i = 0; i <= t; i ++){
				if (y[i] != q){
					dp[i] = max(dp[i], 0);
				}
				for (int j = 0; j < (int)prv[i].size(); j ++){
					if (dp[prv[i][j]] != -1) dp[i] = max(dp[i], dp[prv[i][j]] + 1);
				}
			}
			cout << dp[t] << '\n';
		} else{
			for (int i = 0; i < far[t].size(); i ++){
				if (y[far[t][i].second] != q){
					cout << far[t][i].first << '\n';
					goto done;
				}
			}
			cout << -1 << '\n';
			done: continue;
		}
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:26:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |    for (int k = 0; k < far[x].size(); k ++){
      |                    ~~^~~~~~~~~~~~~~~
bitaro.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for (int j = 0; j < all.size(); j ++){
      |                   ~~^~~~~~~~~~~~
bitaro.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |    for (int i = 0; i < far[t].size(); i ++){
      |                    ~~^~~~~~~~~~~~~~~

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