Submission #479219

#	Time	Username	Problem	Language	Result	Execution time	Memory
479219		s_samchenko	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2070 ms	18784 KiB

bitaro

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define ll long long
#define ff first
#define ss second
#define int ll
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int inf = 1e15;
const int mod = 1e9+7;
const int N = 3e5+100;

vector < vector <int> > g(N);

vector <int> bfs(int v){
	vector <int> d(N, -1); d[v] = 0;
	for (int u = v - 1; u >= 1; --u){
		for (auto to : g[u])
			if (d[to] != -1) d[u] = max(d[u], d[to] + 1);
	}
	return d;
}

void solve(){
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 0; i < m; ++i){
		int a, b; cin >> a >> b;
		g[a].pb(b);
		//g[b].pb(a);
	}
	
	while (q--){
		int t, y;
		cin >> t >> y;
		set <int> c;
		for (int i = 0; i < y; ++i){
			int a; cin >> a; c.insert(a);
		}
		vector <int> d = bfs(t);
		int ans = -1;
		for (int i = 1; i <= n; ++i)
			if (!c.count(i)) ans = max(ans, d[i]);
		//for (int i = 1; i <= n; ++i) cout << d[i] << " "; cout << '\n';
		cout << ans << '\n';
	}
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while (tt--){
		solve();
		cout << '\n';
	}
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 0 / 86