제출 #1031113

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1031113		belgianbot	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	1414 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<bool>> busy(Q, vector<bool>(N, false));
	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][a] = true;
		}
		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++) if (!busy[i][j]) ans = max(ans, dp(j));
			cout << ans << '\n';
		}
		else {
			bool ok = false;
			for (auto x : sol[T[i]]) {
				if (busy[i][x.second]) continue;
				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