제출 #1093955

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1093955		icchou233	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2041 ms	524288 KiB

bitaro

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

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