Submission #479227

#	Time	Username	Problem	Language	Result	Execution time	Memory
479227		s_samchenko	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1796 ms	413168 KiB

bitaro

#include "bits/stdc++.h"

using namespace std;

using ll = long long;

const int SQRT = 350;
const int maxN = 1e5;

int dp[maxN + 5];
vector<int> adj[maxN + 5];
vector<pair<int, int>> root[maxN + 5];

int n, m, q;

void build(){
	vector<int> cost(n + 5, 0);
	vector<int> visited(n + 5, -1);

	for (int i = 1; i <= n; ++i){
		vector<int> r;
		for (int j : adj[i]){
			for (auto e : root[j]){
				int k = e.first, c = e.second;
				if (visited[k] == i)
					cost[k]= max(cost[k], c + 1);
				else{
					r.push_back(k);
					cost[k] = c + 1;
					visited[k] = i;
				}
			}
			if (visited[j] != i){
				r.push_back(j);
				cost[j] = 1;
				visited[j] = i;
			}
		}
		r.push_back(i);

		sort(r.begin(), r.end(), [&](int a, int b){
			return (cost[a] > cost[b]);
		});
		int sz = min(int(r.size()), SQRT);
		for (int j = 0; j < sz; ++j){
			int p = r[j];
			root[i].push_back({p, cost[p]});
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> q;
	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		adj[b].push_back(a);
	}


	build();

	vector<int> queries(n + 5, 0);

	for (int i = 1; i <= q; ++i){
		int t; cin >> t;
		int sz; cin >> sz;
		for (int j = 1; j <= sz; ++j){
			int x; cin >> x;
			queries[x] = i;
		}

		if (sz < SQRT){
			bool f = 0;
			for (auto e : root[t]){
				if (queries[e.first] == i) continue;
				cout << e.second << '\n';
				f = 1;
				break;
			}
			if (!f) cout << -1 << '\n';
		}
		else{
			for (int j = 1; j <= n; ++j){
				if (queries[j] != i) dp[j] = 0;
				else dp[j] = -1;
				for (int k : adj[j])
					if (dp[k] >= 0) dp[j] = max(dp[j], dp[k] + 1);
			}
			cout << dp[t] << '\n';
		}
	}
	return 0;
}

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