Submission #393769

#	Time	Username	Problem	Language	Result	Execution time	Memory
393769		ritul_kr_singh	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1287 ms	214644 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);
	}

	vector<array<int, 2>> dp[n];
	for(int u=0; u<n; ++u) dp[u].push_back({0, u});

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

	for(int u=0; u<n; ++u){
		for(int v : g[u]){
			vector<array<int, 2>> curr;
			array<int, 2> k;
			int i = 0, j = 0, iLim = dp[u].size(), jLim = dp[v].size();
			while((int)curr.size() <= SQRT and (i < iLim or j < jLim)){
				if(i >= iLim){
					k = dp[v][j++];
				}else if(j >= jLim){
					k = dp[u][i++];
					++k[0];
				}else if(dp[u][i][0] + 1 >= dp[v][j][0]){
					k = dp[u][i++];
					++k[0];
				}else{
					k = dp[v][j++];
				}
				filled[k[1]] = true;
				while(i < iLim and filled[dp[u][i][1]]) ++i;
				while(j < jLim and filled[dp[v][j][1]]) ++j;
				curr.push_back(k);
			}
			swap(dp[v], curr);
			for(auto &i : dp[v]) filled[i[1]] = 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(auto &i : dp[x]){
				if(!bad[i[1]]){
					res = max(i[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: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86