Submission #908670

#	Time	Username	Problem	Language	Result	Execution time	Memory
908670		mickey080929	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	661 ms	246756 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

const int B = 300;

int dp[100010][B+1];
int st[100010][B+1];
vector<int> adj[100010];
int idx[100010];
int chk[100010];
int dp2[100010];

int main() {
	int n, m, q;
	cin >> n >> m >> q;
	for (int i=0; i<m; i++) {
		int u, v;
		cin >> u >> v;
		adj[v].push_back(u);
	}
	memset(dp, -1, sizeof(dp));
	for (int i=1; i<=n; i++) {
		for (auto &j : adj[i]) {
			idx[j] = 0;
		}
		for (int j=0; j<B; j++) {
			int mx = -1, pv = -1;
			for (auto &k : adj[i]) {
				while (chk[st[k][idx[k]]]) idx[k] ++;
				if (mx < dp[k][idx[k]]) {
					mx = dp[k][idx[k]];
					pv = k;
				}
			}
			if (pv == -1) {
				dp[i][j] = 0;
				st[i][j] = i;
				break;
			}
			dp[i][j] = mx + 1;
			st[i][j] = st[pv][idx[pv]];
			chk[st[i][j]] = 1;
			idx[pv] ++;
		}
		for (int j=0; j<B; j++) {
			chk[st[i][j]] = 0;
		}
	}
	while (q --) {
		int x;
		cin >> x;
		int k;
		cin >> k;
		vector<int> num(k);
		for (int i=0; i<k; i++) {
			cin >> num[i];
			chk[num[i]] = 1;
		}
		if (k < B) {
			for (int i=0; i<B; i++) {
				if (!chk[st[x][i]]) {
					cout << dp[x][i] << '\n';
					break;
				}
			}
		}
		else {
			for (int i=1; i<=x; i++) {
				if (!chk[i]) dp2[i] = 0;
				else dp2[i] = -1;
				for (auto &j : adj[i]) {
					if (dp2[j] != -1)
						dp2[i] = max(dp2[i], dp2[j] + 1);
				}
			}
			cout << dp2[x] << '\n';
		}
		for (int i=0; i<k; i++) {
			chk[num[i]] = 0;
		}
	}
}

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