Submission #335721

#	Time	Username	Problem	Language	Result	Execution time	Memory
335721		penguinhacker	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1875 ms	414952 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

#define debug(x) cerr << "[" << #x << "] = [" << x << "]\n"

template<class A, class B> ostream& operator<< (ostream& out, pair<A, B> p) {
	return out << '[' << p.first << ", " << p.second << ']';
}

template<class A, int sz> ostream& operator<< (ostream& out, ar<A, sz> a) {
	out << '[';
	for (int i = 0; i < sz; ++i) {
		if (i > 0) out << ", ";
		out << a[i];
	}
	return out << ']';
}

template<class T> ostream& operator<< (ostream& out, vector<T>& v) {
	out << '[';
	for (int i = 0; i < v.size(); ++i) {
		if (i > 0) {
			out << ", ";
		}
		out << v[i];
	}
	return out << ']';
}

const int mxN = 100000;
const int B = 350;
int n, m, q;
bool vis[mxN], bad[mxN];
vector<int> adj[mxN];
vector<pair<int, int>> best[mxN]; // {distance, node}

vector<pair<int, int>> bfs(int start) { // lets fucking nuke this
	vector<int> d(start + 1, -696969);
	d[start] = 0;
	vector<pair<int, int>> res;
	for (int i = start; i >= 0; --i) {
		if (d[i] < 0) continue;
		res.emplace_back(d[i], i);
		for (int j : adj[i]) {
			d[j] = max(d[j], d[i] + 1);
		}
	}
	return res;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> q;
	for (int i = 0; i < m; ++i) {
		int a, b; cin >> a >> b, --a, --b;
		adj[b].push_back(a);
	}
	for (int i = 0; i < n; ++i) {
		best[i].emplace_back(0, i);
		for (int j : adj[i]) {
			vector<pair<int, int>> nxt;
			for (int a = 0, b = 0; nxt.size() < B && (a < best[i].size() || b < best[j].size());) {
				if (b == best[j].size() || (a < best[i].size() && best[i][a] >= make_pair(best[j][b].first + 1, best[j][b].second))) {
					if (!vis[best[i][a].second]) {
						nxt.emplace_back(best[i][a].first, best[i][a].second);
						vis[best[i][a].second] = 1;
					}
					++a;
				}
				else if (a == best[i].size() || (b < best[j].size() && make_pair(best[j][b].first + 1, best[j][b].second) > best[i][a])) {
					if (!vis[best[j][b].second]) {
						nxt.emplace_back(best[j][b].first + 1, best[j][b].second);
						vis[best[j][b].second] = 1;
					}
					++b;
				}
				else assert(0);
			}
			for (auto& x : nxt) vis[x.second] = 0;
			swap(best[i], nxt);
		}
		//debug(best[i]);
	}
	while(q--) {
		int t, y; cin >> t >> y, --t;
		vector<int> cur_bad(y);
		for (int i = 0; i < y; ++i) {
			cin >> cur_bad[i], --cur_bad[i];
			bad[cur_bad[i]] = 1;
		}
		if (y < B) {
			int ans = -1;
			for (pair<int, int>& p : best[t]) {
				if (!bad[p.second]) {
					ans = p.first;
					break;
				}
			}
			cout << ans << "\n";
		}
		else {
			int ans = -1;
			vector<pair<int, int>> cur = bfs(t); // NUKE
			//debug(cur);
			for (pair<int, int>& p : cur) {
				if (!bad[p.second]) {
					ans = max(ans, p.first);
				}
			}
			cout << ans << "\n";
		}
		for (int i : cur_bad) bad[i] = 0;
	}
	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:66:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |    for (int a = 0, b = 0; nxt.size() < B && (a < best[i].size() || b < best[j].size());) {
      |                                              ~~^~~~~~~~~~~~~~~~
bitaro.cpp:66:70: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |    for (int a = 0, b = 0; nxt.size() < B && (a < best[i].size() || b < best[j].size());) {
      |                                                                    ~~^~~~~~~~~~~~~~~~
bitaro.cpp:67:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     if (b == best[j].size() || (a < best[i].size() && best[i][a] >= make_pair(best[j][b].first + 1, best[j][b].second))) {
      |         ~~^~~~~~~~~~~~~~~~~
bitaro.cpp:67:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     if (b == best[j].size() || (a < best[i].size() && best[i][a] >= make_pair(best[j][b].first + 1, best[j][b].second))) {
      |                                 ~~^~~~~~~~~~~~~~~~
bitaro.cpp:74:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     else if (a == best[i].size() || (b < best[j].size() && make_pair(best[j][b].first + 1, best[j][b].second) > best[i][a])) {
      |              ~~^~~~~~~~~~~~~~~~~
bitaro.cpp:74:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     else if (a == best[i].size() || (b < best[j].size() && make_pair(best[j][b].first + 1, best[j][b].second) > best[i][a])) {
      |                                      ~~^~~~~~~~~~~~~~~~

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