Submission #1154619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154619		zhasyn	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2095 ms	17788 KiB

bitaro

#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 2 * 1e5 + 100, M = 4096 + 10, len = 21, inf = 1e18;
const ll mod = 1000002022;
ll um(ll a, ll b){
	return (1LL * a * b) % mod;
}
ll subr(ll a, ll b){
	return ((1LL * a - b) % mod + mod) % mod;
}
vector <int> q[N], rev[N];
bool block[N];
int d[N], b[N], n;
int dj(int x){
	queue <pii> qu;
	for(int i = 1; i <= n; i++){
		d[i] = -1;
	}
	d[x] = 0;
	int ans = -1;
	qu.push({d[x], x});
	while((int)qu.size() != 0){
		int v = qu.front().S, ln = qu.front().F;
		if(block[v] == false) ans = max(ans, d[v]);
		qu.pop();
		if(ln < d[v]) continue;
		for(auto u : rev[v]){
			if(d[u] == -1 || d[u] < d[v] + 1){
				d[u] = d[v] + 1;
				qu.push({d[u], u});
			}
		}
	}
	return ans;
}
int main(){
  	ios::sync_with_stdio(false);
  	cin.tie(NULL);
	int m, g;
	cin >> n >> m >> g;
	for(int i = 0, a, b; i < m; i++){
		cin >> a >> b;
		q[a].pb(b);
		rev[b].pb(a);
	}
	for(int i = 0, t, k; i < g; i++){
		cin >> t >> k;
		for(int j = 0; j < k; j++){
			cin >> b[j];
			block[b[j]] = true;
		}
		// calculations
		cout << dj(t) << endl;
		
		for(int j = 0; j < k; j++){
			block[b[j]] = false;
		}
	}
  return 0;
}
 

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