Submission #1286403

#TimeUsernameProblemLanguageResultExecution timeMemory
1286403samarthkulkarniBitaro’s Party (JOI18_bitaro)C++20
0 / 100
2 ms572 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;
vi adj[MAXN];
ll n;

ll calculate(ll T, set<ll> &hs) {
	vi dist(n+1, -1e18);
	vector<bool> vis(n+1);

	dist[T] = 0;
	ll mx = -1e18;

	priority_queue<pr> q;
	q.push({0, T});

	while (!q.empty()) {
		ll a = q.top().ss; q.pop();
		if (vis[a]) continue;
		vis[a] = true;

		for (auto b : adj[a]) {
			if (dist[a] + 1 > dist[b]) {
				dist[b] = dist[a] + 1;
				q.push({dist[b], b});
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		if (hs.count(i)) continue;
		mx = max(mx, dist[i]);
	}

	return mx;
}


void solution() {
    ll m, q; cin >> n >> m >> q;
    while (m--) {
    	ll a, b; cin >> a >> b;
    	adj[b].push_back(a);
    }

    while (q--) {
    	ll t, y; set<ll> hs;
    	cin >> t >> y;
    	while (y--) {
    		ll x; cin >> x;
    		hs.insert(x);
    	}

    	ll ans = calculate(t, hs);
    	cout << (ans == -1e18 ? -1 : ans) << endl;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...