Submission #1298852

#TimeUsernameProblemLanguageResultExecution timeMemory
1298852muhammad-ahmadBitaro’s Party (JOI18_bitaro)C++20
14 / 100
823 ms189488 KiB
// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <numeric>
#include <cassert>
#include <chrono>
using namespace std;

void fast_io(){
	// freopen("", "r", stdin);
	// freopen("", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(); cout.tie();
	cout << setprecision(9);
}
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second

const int N = 1e5 + 5;

int n, m, q, indeg[N], ans[N]; 
vector<int> topo, adj[N];
vector<pair<int, int>> L[N];

vector<pair<int, int>> merge(vector<pair<int, int>> x, vector<pair<int, int>> y){
	vector<pair<int, int>> z;
	int i = 0, j = 0;
	while (i < (int) x.size() && j < (int) y.size()){
		if (x[i].fi + 1 > y[j].fi) {z.push_back({x[i].fi + 1, x[i].se}); i++;}
		else {z.push_back(y[j]); j++;}
	}
	
	while (i < (int) x.size()) {z.push_back({x[i].fi + 1, x[i].se}); i++;};
	while (j < (int) y.size()) {z.push_back(y[j]); j++;};
	
	int M = z.size();
	vector<pair<int, int>> ans;
	for (int ii = 0; ii < M; ii++){
		if (ii + 1 < M && z[ii].second == z[ii + 1].second) continue;
		ans.push_back(z[ii]);
	}
	
	sort(rall(ans));
	
	while (ans.size() > 100) ans.pop_back();
	return ans;
}

void init(){
	queue<int> q;
	for (int i = 1; i <= n; i++) L[i].push_back({0, i});
	for (int i = 1; i <= n; i++) if (indeg[i] == 0) q.push(i);
	
	while (q.size()){
		int u = q.front(); q.pop();
		topo.push_back(u);
		for (auto v : adj[u]){
			indeg[v]--;
			if (indeg[v] == 0)  q.push(v);
		}
	}
	for (auto u : topo){
		for (auto v : adj[u]){
			L[v] = merge(L[u], L[v]);
		}
	}
}

void solve() {
	cin >> n >> m >> q;
	
	for (int i = 1; i <= m; i++){
		int u, v; cin >> u >> v;
		indeg[v]++;
		adj[u].push_back(v);
	}
	
	init();
	
	for (int Q = 1; Q <= q; Q++){
		int T, Y; cin >> T >> Y;
		int C[Y + 1];
		map<int, bool> c;
		for (int i = 1; i <= Y; i++) {
			cin >> C[i];
			c[C[i]] = 1;
		}
		
		if (Y < 100)
		{
			bool bb = 0;
			int S = min(100, (int) L[T].size());
			for (int i = 0; i < S; i++){
				if (!c[L[T][i].second]){
					cout << L[T][i].first << endl;
					bb = 1;
					break;
				}
			}
			if (!bb) cout << -1 << endl;
		}
		
		else
		{
			for (int i = 1; i <= n; i++) ans[i] = 0;
			for (int i = 1; i <= Y; i++){
				ans[C[i]] = -1e9;
			}
			
			for (auto u : topo){
				for (auto v : adj[u]){
					ans[v] = max(ans[v], ans[u] + 1);
				}
			}
			
			if (ans[T] < 0) cout << -1 << endl;
			else cout << ans[T] << endl;
		}
		
	}

	return;
}

signed main() {
    fast_io();
    srand(chrono::steady_clock::now().time_since_epoch().count());
    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
    return 0;
}



#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...