Submission #67042

#	Time	Username	Problem	Language	Result	Execution time	Memory
67042		szawinis	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	1708 ms	128032 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+1, INF = 1e9+1;

int n, m, q, bsz = 50;
vector<int> g[N];
vector<pair<int,int> > dp[N];
bool blocked[N];
int f[N];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> q;
	for(int i = 0, s, e; i < m; i++) {
		cin >> s >> e;
		--s, --e;
		g[e].push_back(s);
	}
	dp[0].emplace_back(0, 0);
	for(int i = 1; i < n; i++) {
		dp[i].emplace_back(0, i);
		for(int j: g[i]) for(auto x: dp[j]) dp[i].emplace_back(x.first + 1, x.second);
		nth_element(dp[i].begin(), dp[i].begin() + min(bsz + 10, (int) dp[i].size()), dp[i].end(), greater<pair<int,int> >());
		dp[i].resize(min(bsz + 10, (int) dp[i].size()));
	}
	while(q--) {
		int targ, Y;
		cin >> targ >> Y;
		--targ;
		vector<int> C(Y);
		for(int i = 0; i < Y; i++) {
			cin >> C[i];
			--C[i];
			blocked[C[i]] = true;
		}
		int res = -INF;
		if(Y < bsz) {
			for(auto p: dp[targ]) if(!blocked[p.second]) res = max(p.first, res);
		} else {
			fill(f, f+targ+1, 0);
			for(int i: C) f[i] = -INF;
			for(int i = 0; i <= targ; i++) {
				for(int j: g[i]) f[i] = max(f[j] + 1, f[i]);
				if(f[i] < 0) f[i] = -INF;
			}
			res = f[targ];
		}
		if(res == -INF) cout << -1;
		else cout << res;
		cout << '\n';
		for(int i = 0; i < Y; i++) blocked[C[i]] = false;
	}
}

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