Submission #1286502

#TimeUsernameProblemLanguageResultExecution timeMemory
1286502samarthkulkarniBitaro’s Party (JOI18_bitaro)C++20
0 / 100
2094 ms2100 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("fast-math")

#define ll long long
#define ld long double
#define vi vector<ll>
#define endl "\n"
#define pr pair<ll, ll>
#define ff first 
#define ss second
#define all(x) x.begin(), x.end()
const int mod = 1e9+7;
void _p(ll a){cout<<a<<endl;}
void _p(string a){cout<<a<<endl;}
void _p(ld a) {cout<<a<<endl;}
template <class T>
void _p(vector<T> a){for(T val:a)cout<<val<<" ";cout<<endl;}
#define debug(x) cout<<#x<<" -> ";_p(x)

typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update > ordered_set;

vector<pr> move8 = {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};
vector<pr> move4 = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
vector<pr> move2 = {{0, 1}, {1, 0}};

void solution();
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}

const int MAXN = 1e5+10;
bool vis[MAXN];
vi adj[MAXN];
vi radj[MAXN];
ll n, m, q;
ll B;
vector<set<pr>> PDist;


vi ord;
void dfs(ll a) {
	vis[a] = true;
	for (auto b : adj[a]) {
		if (vis[b]) continue;
		dfs(b);
	}
	ord.push_back(a);
}


ll calculate(ll T, set<ll> &temp) {
	vi dist(n+1);
	for (auto val : temp) dist[val] = -1;

	for (auto a : ord) {
		for (auto b : radj[a]) {
			if (dist[b] == -1) continue;
			dist[a] = max(dist[b] + 1, dist[a]);
		}

		if (a == T) break;
	}
	return dist[T];
}


void precomputation() {
	priority_queue<array<ll, 3>> q;

	for (int i = 1; i <= n; i++) {
		q.push({0, i, i});
	}

	while (!q.empty()){
		auto [d, a, h] = q.top(); q.pop();

		if (PDist[a].size() > B+1 && 
			PDist[a].begin()->ff > d) continue; 
		PDist[a].insert({d, h});

		if (PDist[a].size() > B+1) PDist[a].erase(PDist[a].begin());

		for (auto b : adj[a]) {
			q.push({d+1, b, h});
		}
	}
}	





void solution() {
    cin >> n >> m >> q;
    B = sqrt(n);
    PDist.resize(n+1);
    while (m--) {
    	ll a, b; cin >> a >> b;
    	adj[a].push_back(b);
    	radj[b].push_back(a);
    }

   	for (int i = 1; i <= n; i++) {
   		if (!vis[i]) dfs(i);
   	}
   	reverse(all(ord));

   	precomputation();


   	while (q--) {
   		ll T, Y;
   		cin >> T >> Y;
   		set<ll> temp;
   		for (int i = 0; i < Y; i++) {
   			ll x; cin >> x; temp.insert(x);
   		}

   		if (Y >= B) {
   			cout << calculate(T, temp) << endl;
   		} else {
   			ll ans = -1;
   			for (auto [x, y] : PDist[T]) {
   				if (temp.count(y)) continue;
   				ans = max(ans, x);
   			}

   			cout << ans << endl;

   		}
   	}


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