Submission #458808

#	Time	Username	Problem	Language	Result	Execution time	Memory
458808		zeyu	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1384 ms	111736 KiB

bitaro

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
const int B = 120;
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);
 
bool cmp(int x, int y){
	return val[x] > val[y];
}
 
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;
			}
		}
		all.push_back(i);
		sort(all.begin(), all.end(), cmp);
		for (int j = 0; j < min((int)all.size(), B); j ++){
			far[i].push_back(make_pair(val[all[j]], all[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 < (int)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:30: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]
   30 |    for (int k = 0; k < far[x].size(); k ++){
      |                    ~~^~~~~~~~~~~~~~~

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