제출 #1258374

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258374		ssitaram	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2094 ms	10636 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m, q; cin >> n >> m >> q;
	int bl = 100;
	vector<vector<int>> to(n);
	for (int i = 0; i < m; ++i) {
		int a, b; cin >> a >> b;
		to[--a].push_back(--b);
	}
	vector<set<pair<int, int>>> best(n);
	vector<set<pair<int, int>>> bestu(n);
	auto add = [&](int idx, pair<int, int> v) -> void {
		auto it = bestu[idx].lower_bound({v.second, 0});
		if (it != bestu[idx].end() && it->first == v.second) {
			if (it->second >= v.first) return;
			best[idx].erase({it->second, it->first});
			bestu[idx].erase(it);
		}
		best[idx].insert(v);
		bestu[idx].insert({v.second, v.first});
		if (best[idx].size() > bl) {
			it = best[idx].begin();
			bestu[idx].erase({it->second, it->first});
			best[idx].erase(it);
		}
	};
	for (int i = 0; i < n; ++i) {
		add(i, {0, i});
		for (int j : to[i]) {
			for (pair<int, int> k : best[i]) {
				add(j, {k.first + 1, k.second});
			}
		}
	}
	vector<bool> nouse(n);
	vector<int> mx(n);
	vector<int> c(n);
	while (q--) {
		int t, y; cin >> t >> y;
		for (int i = 0; i < y; ++i) {
			cin >> c[i];
			--c[i];
			nouse[c[i]] = true;
		}
		--t;
		if (y >= bl) {
			int ans = -1;
			for (int j = t; j >= 0; --j) {
				mx[j] = (j == t ? 0 : -1);
				for (int k : to[j]) {
					if (k <= t && mx[k] != -1) mx[j] = max(mx[j], mx[k] + 1);
				}
				if (!nouse[j]) ans = max(ans, mx[j]);
			}
			cout << ans << '\n';
		} else {
			auto it = prev(best[t].end());
			while (it != best[t].begin() && nouse[it->second]) {
				--it;
			}
			if (nouse[it->second]) {
				cout << "-1\n";
			} else {
				cout << it->first << '\n';
			}
		}
		for (int i = 0; i < y; ++i) {
			nouse[c[i]] = false;
		}
	}
	return 0;
}

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