제출 #1325637

#제출 시각아이디문제언어결과실행 시간메모리
1325637crispxxBitaro’s Party (JOI18_bitaro)C++20
14 / 100
758 ms411560 KiB
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int B = 447, inf = 1e9 + 5;

bool chmax(int &a, const int &b) {
	return a < b ? a = b, true : false;
}

void solve() {
	int n, m, q; cin >> n >> m >> q;
	
	vector<vector<int>> radj(n);
	
	for(int i = 0; i < m; i++) {
		int u, v; cin >> u >> v;
		u--, v--;
		radj[v].push_back(u);
	}
	
	vector<vector< array<int, 2> >> sql(n);
	
	for(int i = 0; i < n; i++) {
		int sz = radj[i].size();
		
		vector<int> ptr(sz);
		
		for(int it = 0; it < B; it++) {
			int mx = -1, v = -1;
			
			for(int j = 0; j < sz; j++) {
				int from = radj[i][j];
				
				if(ptr[j] < (int)sql[from].size()) {
					if( chmax(mx, sql[from][ptr[j]][0]) ) {
						v = sql[from][ptr[j]][1];
					}
				}
			}
			
			if(v == -1) break;
			
			for(int j = 0; j < sz; j++) {
				int from = radj[i][j];
				
				if(ptr[j] < (int)sql[from].size() && v == sql[from][ptr[j]][1]) {
					sql[i].push_back({mx + 1, v});
					ptr[j]++;
					break;
				}
			}
		}
		
		if(sql[i].size() < B) sql[i].push_back({0, i});
		
		sort(sql[i].begin(), sql[i].end(), greater<>());
	}
	
	vector<int> is(n);
	
	while(q--) {
		int T, Y; cin >> T >> Y;
		
		T--;
		
		vector<int> C(Y);
		
		for(auto &x : C) {
			cin >> x;
			is[--x] = 1;
		}
		
		if(Y <= B) {
			int mx = -1;
			
			for(auto [d, u] : sql[T]) {
				if(!is[u]) {
					mx = d;
					break;
				}
			}
			
			cout << mx << '\n';
		} else {
			vector<int> dp(n);
			
			for(auto &x : C) dp[x] = -inf;
			
			for(int i = 0; i < n; i++) {
				for(auto from : radj[i]) {
					if(dp[from] != -inf) chmax(dp[i], dp[from] + 1);
				}
			}
			
			cout << (dp[T] == -inf ? -1 : dp[T]) << '\n';
		}
		
		for(auto &x : C) is[x] = 0;
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...