Submission #1301943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301943		duyanhchupapi	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1210 ms	110684 KiB

bitaro

#include <bits/stdc++.h>
using namespace std; 
using ll = long long; 
const int N = 1e5 + 5, inf = 2e9;
int n, m, q;
vector <int> g[N];
vector <pair<int, int>> luu[N];
int dp[N], c[N];
bool busy[N];

int main() { 
	ios_base::sync_with_stdio(0); cin.tie(0);
	// freopen(".INP", "r", stdin);
	// freopen(".OUT", "w", stdout);
		
	cin >> n >> m >> q;
	while (m--) {
		int u, v;
		cin >> u >> v;
		g[v].push_back(u);
	}	
	
	int sq = 100;
	for (int u=1;u<=n;++u) {
		vector <pair<int, int>> tmp;
		for (int v : g[u]) {
			for (pair <int, int> P : luu[v]) tmp.push_back(P);
			tmp.emplace_back(0, v);
		}
		
		sort(tmp.begin(), tmp.end(), greater<>());
		for (pair <int, int> P : tmp) {
			if (!busy[P.second]) {
				luu[u].emplace_back(P.first + 1, P.second);
				busy[P.second] = 1;
				if (luu[u].size() == sq) break;
			}
		}
		
		for (pair <int, int> P : luu[u]) busy[P.second] = 0;
	}
	
	while (q--) {
		int t, y, ans = -1;
		cin >> t >> y;
		for (int i=1;i<=y;++i) cin >> c[i], busy[c[i]] = 1;
		if (!busy[t]) ans = 0;
		
		if (y >= sq) {
			fill(dp, dp+n+1, -inf);
			dp[t] = 0;
			for (int u=t;u>=1;--u) {
				for (int v : g[u]) dp[v] = max(dp[u] + 1, dp[v]);
			}
			
			for (int i=1;i<=t;++i) if (!busy[i]) ans = max(ans, dp[i]);
		}
		else {
			for (pair <int, int> P : luu[t]) 
				if (!busy[P.second]) ans = max(ans, P.first);
		}
		
		for (int i=1;i<=y;++i) busy[c[i]] = 0;
		cout << ans << '\n';	
	}

}

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