Submission #235319

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

bitaro

#include <cstdio>
#include <algorithm>
#include <vector>

const int Inf = 0x3f3f3f3f;
const int MN = 100005, MS = 100005, B = 300 /* sqrt(MS) */, MB = B + 5;

int N, M, Q, banb[MN], ban[MN];
std::vector<int> G[MN];

int V[MN][MB], D[MN][MB], tV[MB], tD[MB], vis[MN];
void Prework() {
	int id = 0;
	for (int i = 1; i <= N; ++i) {
		V[i][1] = i, D[i][1] = 0;
		for (int j : G[i]) {
			++id;
			int x = 1, y = 1, z = 0;
			while (V[i][x] && V[j][y] && z < B) {
				int v, d;
				if (D[i][x] > D[j][y]) v = V[i][x], d = D[i][x], ++x;
				else v = V[j][y], d = D[j][y] + 1, ++y;
				if (vis[v] != id)
					vis[v] = id, ++z,
					tV[z] = v, tD[z] = d;
			}
			while (V[i][x] && z < B) {
				int v = V[i][x], d = D[i][x]; ++x;
				if (vis[v] != id)
					vis[v] = id, ++z,
					tV[z] = v, tD[z] = d;
			}
			while (V[j][y] && z < B) {
				int v = V[j][y], d = D[j][y] + 1; ++y;
				if (vis[v] != id)
					vis[v] = id, ++z,
					tV[z] = v, tD[z] = d;
			}
			for (int k = 1; k <= z; ++k)
				V[i][k] = tV[k], D[i][k] = tD[k];
		}
	}
}

int f[MN];

int main() {
	scanf("%d%d%d", &N, &M, &Q);
	for (int i = 1; i <= M; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		G[y].push_back(x);
	}
	Prework();
	while (Q--) {
		int s, c;
		scanf("%d%d", &s, &c);
		for (int i = 1; i <= c; ++i) scanf("%d", &ban[i]), banb[ban[i]] = 1;
		if (c < B) {
			int ans = -1;
			for (int i = 1; V[s][i]; ++i)
				if (!banb[V[s][i]]) {
					ans = D[s][i];
					break;
				}
			printf("%d\n", ans);
		} else {
			f[s] = 0;
			for (int i = 1; i < s; ++i) f[i] = -Inf;
			for (int i = s; i > 1; --i)
				for (int j : G[i])
					f[j] = std::max(f[j], f[i] + 1);
			int ans = -1;
			for (int i = 1; i <= s; ++i)
				if (!banb[i]) ans = std::max(ans, f[i]);
			printf("%d\n", ans);
		}
		for (int i = 1; i <= c; ++i) banb[ban[i]] = 0;
	}
	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &s, &c);
   ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:58:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 1; i <= c; ++i) scanf("%d", &ban[i]), banb[ban[i]] = 1;
                                ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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