Submission #1301930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301930		duyanhchupapi	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	1349 ms	169832 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], adj[N];
int topo[N], deg[N], dp[N], c[N], f[403][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[u].push_back(v);
		adj[v].push_back(u);
		deg[v]++;
	}	
	
	queue <int> q;
	for (int i=1;i<=n;++i) if (deg[i] == 0) q.push(i);
	int idd = 0;
	while (!q.empty()) {
		int u = q.front();
		topo[++idd] = u;
		q.pop();
		for (int v : g[u]) if (--deg[v] == 0) q.push(v);
	}
	
	int sq = 200, mq = min(n, 400);
	for (int i=1;i<=mq;++i) {
		int u = topo[i];
		fill(f[i], f[i]+n+1, -inf);
		f[i][u] = 0;
		for (int j=1;j<=n;++j) {
			int v = topo[j];
			for (int x : g[v]) f[i][x] = max(f[i][x], f[i][v] + 1);
		}
	}
	
	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 (y >= sq) {
			fill(dp, dp+n+1, -inf);
			dp[t] = 0;
			for (int i=n;i>=1;--i) {
				int u = topo[i];
				for (int v : adj[u]) dp[v] = max(dp[u] + 1, dp[v]);
			}
			
			for (int i=1;i<=n;++i) if (!busy[i]) ans = max(ans, dp[i]);
		}
		else {
			for (int i=1;i<=mq;++i) 
				if (!busy[topo[i]]) ans = max(ans, f[i][t]);
		}
		
		for (int i=1;i<=y;++i) busy[c[i]] = 0;
		cout << ans << '\n';	
	}

}

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