Submission #1031072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031072		belgianbot	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2051 ms	11612 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

int N, M, Q;
vector<vector<int>> adj;
vector<int> memo;
int goal;

int dp(int pos) {
	if (pos > goal) return INT_MIN;
	if (pos == goal) return 0;
	
	if (memo[pos] != -1) return memo[pos];
	int ans = INT_MIN;
	for (int x : adj[pos]) {
		ans = max(ans, dp(x) + 1);
	}
	
	return memo[pos] = ans;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M >> Q;
	adj.resize(N);
	
	for (int i = 0; i < M; i++) {
		int a, b; cin >> a >> b; a--; b--;
		adj[a].push_back(b);
	}
	
	while (Q--) {
		int T, Y; cin >> T >> Y; T--;
		vector<bool> busy(N, false);
		for (int i = 0; i < Y; i++) {
			int a; cin >> a; a--;
			busy[a] = true;
		}
		goal = T;
		memo.clear(); memo.resize(T, -1);
		int ans = -1;
		for (int i = 0; i <= T; i++) if (!busy[i])ans = max(ans, dp(i));
		cout << ans << '\n';
	} 
			
	
	return 0;
}
			

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