Submission #393737

#	Time	Username	Problem	Language	Result	Execution time	Memory
393737		ritul_kr_singh	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	8 ms	1932 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define sp << ' ' <<
#define nl << '\n'
 
const int INF = 1e9, SQRT = 200, MAXN = 1e5;
const array<int, 2> DEF = {-INF, -1};

signed main(){
	cin.tie(0)->sync_with_stdio(0);

	int n, m, q, x, y; cin >> n >> m >> q;
	vector<int> g[n];
	while(m--){
		cin >> x >> y;
		g[x-1].push_back(y-1);
	}

	array<int, 2> dp[SQRT][n];
	for(int j=0; j<SQRT; ++j) fill(dp[j], dp[j]+n, DEF);
	for(int u=0; u<n; ++u) dp[0][u] = {0, u};

	bool filled[n]; fill(filled, filled+n, false);

	for(int u=0; u<n; ++u){
		for(int v : g[u]){
			array<int, 2> curr[SQRT];
			int i = 0, j = 0;
			for(auto &k : curr){
				while(i < SQRT and dp[i][u][1]>=0 and filled[dp[i][u][1]]) ++i;
				while(j < SQRT and dp[j][v][1]>=0 and filled[dp[j][v][1]]) ++j;
				if(i >= SQRT){
					k = dp[j++][v];
				}else if(j >= SQRT){
					k = dp[i++][u];
					++k[0];
				}else if(dp[i][u][0] + 1 >= dp[j][v][0]){
					k = dp[i++][u];
					++k[0];
				}else{
					k = dp[j++][v];
				}
				filled[max(k[1], 0)] = true;
			}
			for(i=0; i<SQRT; ++i) dp[i][v] = curr[i], filled[max(curr[i][1], 0)] = false;
		}
	}

	bool bad[n]; fill(bad, bad+n, false);

	while(q--){
		cin >> x >> y; --x;
		int c[y]; for(int &i : c) cin >> i, --i, bad[i] = true;

		int res = -1;

		if(y < SQRT){
			for(int i=0; i<SQRT; ++i){
				if(!bad[dp[i][x][1]]){
					res = max(dp[i][x][0], res);
					break;
				}
			}
		}else{
			int longest[n];
			for(int u=n-1; u>=0; --u){
				longest[u] = -INF;
				if(u == x) longest[u] = 0;
				if(u >= x) continue;

				for(int v : g[u]){
					longest[u] = max(longest[u], longest[v] + 1);
				}

				if(!bad[u]) res = max(res, longest[u]); 
			}
		}

		cout << res nl;
		for(int i : c) bad[i] = false;
	}
}

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