Submission #1325641

#TimeUsernameProblemLanguageResultExecution timeMemory
1325641crispxxBitaro’s Party (JOI18_bitaro)C++20
14 / 100
2094 ms6920 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]) {
					chmax(dp[i], dp[from] + 1);
				}
			}
			
			if(dp[T] < 0) dp[T] = -1;
			
			cout << 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...