제출 #1329177

#제출 시각아이디문제언어결과실행 시간메모리
1329177m_bezrutchkaBitaro’s Party (JOI18_bitaro)C++20
0 / 100
1 ms344 KiB
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 7;
const int MAXN = 1e5 + 10;
const int SQRT = 0;

vector<int> adj[MAXN];
int n, m, q;

int dp[MAXN];
bool seen[MAXN];
bool bad[MAXN];

void build() {
	return;
}

void dfs_large(int v, int target) {
	seen[v] = true;
	if (v == target) dp[v] = 0;
	for (int w: adj[v]) {
		if (!seen[w]) dfs_large(w, target);
		dp[v] = max(dp[v], dp[w] + 1);
	}
}

int solve_small(int target, vector<int> &busy) {
	return -INF;
}

int solve_large(int target, vector<int> &busy) {
	for (int i = 1; i <= n; i++) {
		seen[i] = false;
		bad[i] = false;
		dp[i] = -INF;
	}
	for (int x: busy) {
		bad[x] = true;
	}

	int resp = -1;
	for (int i = 1; i <= n; i++) {
		if (!bad[i]) {
			dfs_large(i, target);
			resp = max(resp, dp[i]);
		}
	}
	return resp;
}

int query(int target, vector<int> &busy) {
	int sz = (int) busy.size();
	if (sz <= SQRT) return solve_small(target, busy);
	else return solve_large(target, busy);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

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

	build();

	while (q--) {
		int t, cnt; cin >> t >> cnt;
		vector<int> busy;
		while (cnt--) {
			int x; cin >> x;
			busy.push_back(x);
		}
		cout << query(t, busy) << endl;
	}

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...