Submission #458731

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

bitaro

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
const int B = 250;
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;
		vector<int> dist[B];
		for (int j = 0; j < (int)prv[i].size(); j ++){
			int x = prv[i][j];
			for (int k = 0; k < (int)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);
		val[i] = 0;
		for (int j = 0; j < (int)all.size(); j ++){
			if (val[all[j]] < B) dist[val[all[j]]].push_back(all[j]);
		}
		int cnt = 0;
		for (int k = B - 1; k >= 0; k --){
			for (int j = 0; j < (int)dist[k].size(); j ++){
				far[i].push_back(make_pair(k, dist[k][j]));
				cnt ++;
				if (cnt == B) goto flag;
			}
		}
		flag: continue;
	}
	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;
		}
	}
}

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