Submission #383421

#	Time	Username	Problem	Language	Result	Execution time	Memory
383421		thiago4532	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2078 ms	7916 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 10;
int n, m, q, dist[maxn], grau[maxn], grau2[maxn];
vector<int> grafo[maxn];
bool mark[maxn];

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		if (a > b) swap(a, b);

		grafo[a].push_back(b);
		grau[b]++;
	}

	for (int i = 1; i <= q; i++) {
		memset(mark, 0, sizeof maxn);
		memset(dist, 0, sizeof maxn);
		memcpy(grau2, grau, sizeof maxn);

		int t, y;
		cin >> t >> y;
		vector<int> query(y);
		for (int i = 0; i < y; i++)
			cin >> query[i], mark[ query[i] ] = true;
		queue<int> fila;
		for (int i = 1; i <= n; i++)
			if (grau2[i] == 0) fila.push(i);

		while (!fila.empty()) {
			int u = fila.front();
			fila.pop();

			for(auto v : grafo[u]) {
				grau2[v]--;
				if (grau2[v] == 0) fila.push(v);

				if (dist[u] > 0 || !mark[u])
					dist[v] = max(dist[v], dist[u] + 1);
			}
		}
		if (dist[t] == 0 && mark[t]) cout << "-1\n";
		else cout << dist[t] << '\n';
	}	
	return 0;
}

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