제출 #1031120

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1031120		belgianbot	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	1419 ms	524288 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)) dec[i] = true;
	}
	
	vector<set<pair<int,int>>> sol(N);
	for (int i = 0; i < N; i++) {
		sol[i].insert({0,i});
		for (int j : revAdj[i]) {
			sol[i].insert({-1,j});
			int cnt = 0;
			for (auto x : sol[j]) {
				if (cnt >= sqrt(N)) break;
				cnt++;
				sol[i].insert({x.first - 1, x.second});
			}
		}
	}
	
	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: 0 / 7
• Subtask 3: 0 / 86