Submission #1031291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031291		belgianbot	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1150 ms	425556 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

int N, M, Q;
vector<vector<int>> adj, revAdj;
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); revAdj.resize(N);
	
	for (int i = 0; i < M; i++) {
		int a, b; cin >> a >> b; a--; b--;
		adj[a].push_back(b);
		revAdj[b].push_back(a);
	}
	
	vector<vector<int>> busy(Q);
	vector<bool> dec(Q, false);
	vector<int> T(Q);
	for (int i = 0; i < Q; i++) {
		cin >> T[i]; T[i]--;
		int Y; cin >> Y;
		for (int j = 0; j < Y; j++) {
			int a; cin >> a; a--;
			busy[i].push_back(a);
		}
		if (Y < sqrt(N) + 100) dec[i] = true;
	}
	
	vector<vector<pair<int,int>>> sol(N);
	for (int i = 0; i < N; i++) {
			vector<bool> processed(i, false);
			vector<int> it(int(revAdj[i].size()), 0);
			for (int k = 0; k < sqrt(N) + 100; k++) {
				pair<int,int> best = {INT_MAX, -1};
				int index = -1;
				for (int j = 0; j < int(revAdj[i].size()); j++) {
					int pos = revAdj[i][j];
					while (it[j] < int(sol[pos].size()) && processed[sol[pos][it[j]].second]) it[j]++;
					if (it[j] < int(sol[pos].size()) && sol[pos][it[j]] < best) {
						best = sol[pos][it[j]];
						index = j;
					}
				}
				if (index != -1) {
					best.first--;
					it[index]++;
					sol[i].push_back(best);
					processed[best.second] = true;
				}
			}
			sol[i].push_back({0,i});
	}
	
	for (int i = 0; i < Q; i++) {
		if (!dec[i]) {
			goal = T[i];
			memo.clear(); memo.resize(T[i], -1);
			int ans = -1;
			for (int j = 0; j <= goal; j++) {
				auto it = lower_bound(busy[i].begin(), busy[i].end(), j);
				if (it == busy[i].end() || (*it) != j) ans = max(ans, dp(j));
			}
			cout << ans << '\n';
		}
		else {
			bool ok = false;
			for (auto x : sol[T[i]]) {
				auto it = lower_bound(busy[i].begin(), busy[i].end(), x.second);
				if (it == busy[i].end() || (*it) != x.second) {
					ok = true;
					cout << -x.first << '\n';
					break;
				}
			}
			if (!ok) cout << -1 << '\n';
		}
	} 
			
	
	return 0;
}
			

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