Submission #988138

#	Time	Username	Problem	Language	Result	Execution time	Memory
988138		icchou233	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	6 ms	2652 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 = 1e6;
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++) {
		for (int e: canals[i]) {
			bitset<MAXN+1> used;
			auto it1 = begin(blocks[i]), it2 = begin(blocks[e]);
			while (it2 != end(blocks[e])) {
				while (it1 != end(blocks[i]) && used[it1 -> second]) {
					it1++;
					blocks[i].erase(prev(it1));
				}
				while (it2 != end(blocks[e]) && used[it2 -> second]) {
					it2++;
				}
				if (it1 == end(blocks[i]) && it2 == end(blocks[e])) {
					break;
				}
				if (it1 == end(blocks[i]) || (it2 != end(blocks[i]) 
					&& it2 -> first <= it1 -> first)) {
					used[it2 -> second] = true;
					blocks[i].insert({it2 -> first - 1, it2 -> second});
					if (blocks[i].size() > blockLen) {
						blocks[i].erase(prev(end(blocks[i])));
					}
					it2++;
				} else {
					used[it1 -> second] = true;
					it1++;
				}
			}
		}
		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