Submission #1298856

#TimeUsernameProblemLanguageResultExecution timeMemory
1298856muhammad-ahmadBitaro’s Party (JOI18_bitaro)C++20
7 / 100
873 ms589824 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];
bool vis[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() && z.size() < 100){
		if (x[i].fi + 1 > y[j].fi) {
			if (vis[x[i].se]) i++;
			else {
				z.push_back({x[i].fi + 1, x[i].se});
				vis[x[i].se] = 1;
				i++;
			}
		}
		else {
			if (vis[y[j].se]) j++;
			else{
				z.push_back(y[j]);
				vis[y[j].se] = 1;
				j++;
			}
		}
	}
	
	while (i < (int) x.size()) {
		if (vis[x[i].se]) i++;
		else {
			z.push_back({x[i].fi + 1, x[i].se});
			vis[x[i].se] = 1;
			i++;
		}
	}
	while (j < (int) y.size()) {
		if (vis[y[j].se]) j++;
		else{
			z.push_back(y[j]);
			vis[y[j].se] = 1;
			j++;
		}
	}
	
	for (auto i : z) vis[i.se] = 0;
	
	return z;
}

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]){
					if (ans[u] < 0) continue;
					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...