Submission #563718

#	Time	Username	Problem	Language	Result	Execution time	Memory
563718		thiago_bastos	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2069 ms	137628 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;

const int N = 318;
const int K = 10;
const int INF = 1e9;

int st[K][N];

int lg(int x) {
	return x ? 31 - __builtin_clz(x) : 0;
}

void sparse_table(vector<int>& a) {
	int n = a.size();
	int k = 1 + lg(n);

	for(int i = 0; i < n; ++i) st[0][i] = a[i];

	for(int i = 1; i < k; ++i)
	for(int j = 0; j + (1 << i) <= n; ++j)
		st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);	
}

int st_query(int l, int r) {
	int k = 31 - __builtin_clz(r - l + 1);
	return max(st[k][l], st[k][r - (1 << k) + 1]);
}
	
void solve() {
	int n, m, q;

	cin >> n >> m >> q;

	vector<vector<int>> g(n), busy(q), query(n);
	vector<int> ans(q, -1);

	for(int i = 0; i < m; ++i) {
		int s, t;
		cin >> s >> t;
		--s, --t;
		g[s].push_back(t);
	}
	
	for(int i = 0; i < q; ++i) {
		int x, y;
		cin >> x >> y;
		busy[i].resize(y + 2);
		busy[i][0] = -1, busy[i][y + 1] = n;
		for(int j = 1; j <= y; ++j) {
			cin >> busy[i][j];
			--busy[i][j];
		}
		query[--x].push_back(i);
	}

	int L = sqrt(n) + 1;
	
	vector<vector<int>> dp(n);

	for(int i = 0; i < n; ++i) dp[i].resize(L);

	for(int i = 0; i < n; i += L) {
		for(auto& X : dp) fill(X.begin(), X.end(), -INF);

		int hi = min(n, i + L);

		for(int j = i; j < hi; ++j) dp[j][j - i] = 0;

		for(int j = i; j < n; ++j)
			for(int k : g[j])
				for(int x = 0; x < L; ++x)
					dp[k][x] = max(dp[k][x], dp[j][x] + 1);

		for(int v = 0; v < n; ++v) {
			auto& Y = query[v];
			if(Y.empty()) continue;
			sparse_table(dp[v]);
			for(int k : Y) {
				auto& X = busy[k];
				for(int j = 1; j < (int)X.size(); ++j) {
					int l = max(i, X[j - 1] + 1), r = min(hi - 1, X[j] - 1);
					if(l > r) continue;
					ans[k] = max(ans[k], st_query(l - i, r - i));
				}
			}
		}
	}

	for(int x : ans) cout << x << '\n';
}

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

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