Submission #1298146

#TimeUsernameProblemLanguageResultExecution timeMemory
1298146muhammad-ahmadBitaro’s Party (JOI18_bitaro)C++20
7 / 100
2118 ms553568 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 <stack>
#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 int long long
#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]; 
vector<int> adj[N];
vector<pair<int, int>> L[N];

vector<pair<int,int>> merge(const vector<pair<int,int>>& A, const vector<pair<int,int>>& B) {
    static pair<int,int> tmp[700]; // temporary buffer
    int k = 0;
    for(auto &x : A) tmp[k++] = {x.first + 1, x.second};
    for(auto &y : B) tmp[k++] = {y.first, y.second};

    sort(tmp, tmp + k, [](auto &a, auto &b){ return a.second < b.second; });

    vector<pair<int,int>> out;
    out.reserve(300);

    for(int i = 0; i < k; ) {
        int src = tmp[i].second, best = tmp[i].first, j = i + 1;
        while(j < k && tmp[j].second == src) {
            best = max(best, tmp[j].first);
            j++;
        }
        out.push_back({best, src});
        i = j;
    }

    sort(out.rbegin(), out.rend()); // sort descending by length
    if(out.size() > 300) out.resize(300);
    return out;
}

void init(){
	int IN[N];
	for (int i = 1; i <= n; i++) IN[i] = indeg[i];
	queue<int> q;
	for (int i = 1; i <= n; i++){
		L[i].push_back({0, i});
		if (IN[i] == 0) q.push(i);
	}
	
	while (q.size()){
		int u = q.front(); q.pop();
		for (auto v : adj[u]){
			L[v] = merge(L[u], L[v]);
			--IN[v];
			if (IN[v] == 0) q.push(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 i = 1; i <= n; i++) sort(rall(L[i]));
	
	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 <= 300)
		{
			bool bb = 0;
			int S = min(300ll, (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
		{
			queue<int> q;
			int IN[N] = {}, ans[N] = {};
			
			for (int i = 1; i <= Y; i++){
				ans[C[i]] = -1e18;
			}
			
			for (int i = 1; i <= n; i++) IN[i] = indeg[i];
			for (int i = 1; i <= n; i++){
				if (IN[i] == 0) q.push(i);
			}
			
			while (q.size()){
				int u = q.front(); q.pop();
				for (auto v : adj[u]){
					ans[v] = max(ans[v], ans[u] + 1);
					IN[v]--;
					if (IN[v] == 0) q.push(v);
				}
			}
			
			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...