Submission #1031189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031189		belgianbot	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2072 ms	432588 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) - 230) dec[i] = true;
	}
	
	vector<set<pair<int,int>>> sol(N);
	for (int i = 0; i < N; i++) {
		sol[i].insert({0,i});
			vector<set<pair<int,int>>::iterator> it(int(revAdj[i].size()));
			for (int k = 0; k < int(revAdj[i].size()); k++) it[k] = sol[revAdj[i][k]].begin();
			for (int k = 0; k < sqrt(N) - 230; k++) {
				pair<int,int> best = {INT_MAX, -1};
				int index = -1;
				for (int j = 0; j < int(revAdj[i].size()); j++) {
					if (it[j] != sol[revAdj[i][j]].end() && *it[j] < best) {
						best = *it[j];
						best.first--;
						index = j;
					}
				}
				if (index != -1) {
					it[index]++;
					sol[i].insert(best);
				}
			}
	}
	
	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: 0 / 86