제출 #1161238

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161238		crispxx	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	2090 ms	14276 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m, q; cin >> n >> m >> q;
	
	vector<vector<int>> adj(n);
	
	for(int i = 0; i < m; i++) {
		int u, v; cin >> u >> v;
		adj[--u].pb(--v);
	}
	
	vector<int> ord, used(n);
	
	auto dfs = [&](auto &&self, int v) -> void {
		if(used[v]) return;
		used[v] = 1;
		
		for(auto to : adj[v]) {
			self(self, to);
		}
		
		ord.pb(v);
	};
	
	for(int i = 0; i < n; i++) {
		dfs(dfs, i);
	}
	
	reverse(all(ord));
	
	while(q--) {
		int f, k; cin >> f >> k;
		
		f--;
		
		vector<int> dp(n), c(n);
		
		while(k--) {
			int x; cin >> x;
			c[--x] = 1;
			dp[x] = -1e18;
		}
		
		for(auto v : ord) {
			// cout << v + 1 << ": ";
			
			for(auto to : adj[v]) {
				dp[to] = max(dp[to], dp[v] + 1);
			}
			
			// for(int i = 0; i < n; i++) {
				// cout << dp[i] << ' ';
			// }
			
			// cout << nl;
		}
		
		cout << (dp[f] < 0 ? -1 : dp[f]) << nl;
	}
}

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