Submission #712323

#	Time	Username	Problem	Language	Result	Execution time	Memory
712323		Radin_Zahedi2	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	753 ms	244972 KiB

bitaro

#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
#define endl '\n'
const int mod = 1e9 + 7;
const int inf = 2e9 + 5;
const ll linf = 9e18 + 5;


int n, m, q;
const int N = 1e5 + 5;
const int M = 2e5 + 5;
const int S = 300;
vector<int> adj[N];

pair<int, int> vert[N][S];

bool ok[N];

void init() {
	fill(ok + 0, ok + N, true);
}

void input() {
	cin >> n >> m >> q;

	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;

		adj[v].pb(u);
	}
}

void cre() {
	for (int u = 1; u <= n; u++) {
		int inds[sz(adj[u])];
		fill(inds + 0, inds + sz(adj[u]), 0);

		int ind = 0;
		while (ind < S) {
			int bestind = -1;
			pair<int, int> best = mp(-1, 0);

			for (int i = 0; i < sz(adj[u]); i++) {
				while (inds[i] < S) {
					if (ok[vert[adj[u][i]][inds[i]].se]) {
						break;
					}

					inds[i]++;
				}

				if (inds[i] == S) {
					continue;
				}

				if (best < vert[adj[u][i]][inds[i]]) {
					bestind = i;
					best = vert[adj[u][i]][inds[i]];
				}
			}

			if (bestind == -1) {
				break;
			}

			best.fi++;
			vert[u][ind] = best;
			ok[best.se] = false;
			ind++;
		}

		if (ind < S) {
			vert[u][ind] = mp(0, u);
			ind++;
		}
		while (ind < S) {
			vert[u][ind] = mp(-1, 0);
			ind++;
		}


		for (int i = 0; i < S; i++) {
			ok[vert[u][i].se] = true;
		}
	}
}

int naive(int k) {
	int dp[k + 1];
	for (int u = 1; u <= k; u++) {
		if (ok[u]) {
			dp[u] = 0;
		}
		else {
			dp[u] = -inf;
		}

		for (auto v : adj[u]) {
			dp[u] = max(dp[u], dp[v] + 1);
		}
	}

	return max(dp[k], -1);
}

void solve() {
	cre();

	fill(ok + 0, ok + n + 1, true);
	while (q--) {
		int t, y;
		cin >> t >> y;
		
		int verts[y];
		for (int i = 0; i < y; i++) {
			cin >> verts[i];
		}


		for (int i = 0; i < y; i++) {
			ok[verts[i]] = false;
		}

		if (y >= S) {
			cout << naive(t) << endl;
		}
		else {
			for (int i = 0; i < S; i++) {
				if (ok[vert[t][i].se]) {
					cout << vert[t][i].fi << endl;
					break;
				}
			}
		}

		for (int i = 0; i < y; i++) {
			ok[verts[i]] = true;
		}
	}
}

void output() {
}

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

	int number_of_testcases = 1;
	//cin >> number_of_testcases;
	while (number_of_testcases--) {
		init();

		input();

		solve();

		output();
	}

	return 0;
}

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