Submission #988151

#	Time	Username	Problem	Language	Result	Execution time	Memory
988151		icchou233	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	2095 ms	604 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
using PII = pair<int,int>;
#define all(a) begin(a), end(a)
constexpr int blockLen = 100;
constexpr int MAXN = 1e5;
int main() {
  	cin.tie(0) -> sync_with_stdio(0);
  	int n,m,q; cin >> n >> m >> q;
	vector<vector<int>> canals(n + 1);
	while (m--) {
		int s,e; cin >> s >> e;
		canals[e].push_back(s);
	}
	vector<set<PII>> blocks(n + 1);
	for (int i = 1; i <= n; i++) {
		bitset<MAXN + 1> dist;
		int currDist = 0;
		blocks[i].insert({0, i});
		for (int e: canals[i]) {
			for (PII p: blocks[e]) {
				if (p.first > dist[p.second] || p.first - 1 > currDist) {
					continue;
				}
				if (blocks[i].size() >= blockLen) {
					auto it = prev(end(blocks[e]));
					dist[it -> second] = 0;
					blocks[i].erase(it);
					it = prev(end(blocks[i]));
					currDist = it -> first;
				}
				else if (dist[p.second] < 0) {
					blocks[i].erase({dist[p.second], p.second});
				}
				blocks[i].insert({p.first - 1, p.second});
				dist[p.second] = p.first - 1;
			}
		}
		if (blocks[i].size() < blockLen) {
			blocks[i].insert({0, i});
		}
	}
	while (q--) {
		int t,y; cin >> t >> y;
		bitset<MAXN + 1> busy;
		for (int i = 0; i < y; i++) {
			int a; cin >> a;
			busy[a] = 1;
		}
		if (y >= blockLen) {
			vector<int> dp(t+1, -1);
			for (int i = 1; i <= t; i++) {
				if (!busy[i]) {
					dp[i] = max(dp[i], 0);
				}
				for (int e: canals[i]) {
					if (dp[e] != -1) {
						dp[i] = max(dp[i], dp[e] + 1);
					}
				}
			}
			cout << dp[t] << '\n';
		}
		else {
			bool found = false;
			for (PII p: blocks[t]) {
				if (!busy[p.second]) {
					found = true;
					cout << (-1 * p.first) << '\n';
					break;
				}
			}
			if (!found) cout << "-1\n";
		}
	}
}

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