Submission #986727

#	Time	Username	Problem	Language	Result	Execution time	Memory
986727		icchou233	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	1839 ms	485592 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++) {
		sort(all(canals[i]));
		reverse(all(canals[i]));
		bitset<MAXN+1> taken;
		for (int e: canals[i]) {
			if (!taken[e]) {
				taken[e] = true;
				for (PII p: blocks[e]) {
					blocks[i].insert({p.first - 1, p.second});
					if (blocks[i].size() > blockLen) {
						blocks[i].erase(prev(end(blocks[i])));
					}
				}
			}
		}
		if (blocks[i].size() < blockLen) {
			blocks[i].insert({0, i});
		}
	}
	while (q--) {
		int t,y; cin >> t >> y;
		set<int> busy;
		for (int i = 0; i < y; i++) {
			int a; cin >> a;
			busy.insert(a);
		}
		if (y >= blockLen) {
			vector<int> dp(t+1);
			for (int b: busy) {
				if (b <= t) {
					dp[b] = -1;
				}
			}
			for (int i = 1; i <= t; i++) {
				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]) {
				auto it = busy.find(p.second);
				if (it == end(busy)) {
					found = true;
					cout << (-1 * p.first) << '\n';
					break;
				}
			}
			if (!found) cout << "-1\n";
		}
	}
}

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