Submission #656203

#	Time	Username	Problem	Language	Result	Execution time	Memory
656203		Dorost	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	858 ms	267612 KiB

bitaro

/* 	* In the name of GOD  */

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
#define F first
#define S second
#define mk make_pair
const int N = 101234, SQ = 323;
pii mx[N][SQ];
pii c[SQ];
bool f[N];
vector <int> in[N], out[N];
int dp[N];
vector <int> dis[N];

void merge (int a, int b) {
	int in1 = 0, in2 = 0;
	for (int i = 0; i < SQ; i++) {
		while (mx[a][in1].S != -1 && f[mx[a][in1].S])
			in1++;
		while (mx[b][in2].S != -1 && f[mx[b][in2].S])
			in2++;
		if (mx[b][in2].F == -1)
			c[i] = max(mx[a][in1], mk(mx[b][in2].F, mx[b][in2].S));
		else
			c[i] = max(mx[a][in1], mk(mx[b][in2].F + 1, mx[b][in2].S));
		if (c[i].S != -1)
			f[c[i].S] = true;
	}
	for (int i = 0; i < SQ; i++) {
		if (c[i].S != -1)
			f[c[i].S] = false;
		mx[a][i] = c[i];
	}
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie();
	cout.tie();
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		out[a].push_back(b);
		in[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) {
		mx[i][0] = {0, i};
		for (int j = 1; j < SQ; j++)
			mx[i][j] = {-1, -1};
		for (int k : in[i])
			merge (i, k);
	}
	while (q--) {
		int v, sz;
		cin >> v >> sz;
		vector <int> wef(sz);
		for (int i = 0; i < sz; i++) {
			cin >> wef[i];
			f[wef[i]] = true;
		}
		if (sz < SQ) {
			for (int i = 0; i < SQ; i++) {
				if (mx[v][i].S == -1 || !f[mx[v][i].S]) {
					cout << mx[v][i].F << '\n';
					break;
				}
			}
		} else {
			for (int i = 1; i <= n; i++)
				dp[i] = -N;
			dp[v] = 0;
			for (int i = v - 1; i >= 0; i--) 
				for (int j : out[i])
					dp[i] = max(dp[i], dp[j] + 1);
			int ans = -1;
			for (int i = 1; i <= n; i++) 
				if (!f[i])
					ans = max(ans, dp[i]);
			cout << ans << '\n';
		}
		for (int i = 0; i < sz; i++) {
			f[wef[i]] = false;
		}
	}
}

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