Submission #426548

#	Time	Username	Problem	Language	Result	Execution time	Memory
426548		milleniumEeee	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1905 ms	255344 KiB

bitaro

#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
#define ll long long
#define mk make_pair
template<class T>void chmax(T &a, T b){if (a < b)a = b;}
template<class T>void chmin(T &a, T b){if (b < a)a = b;}

using namespace std;

const int MAX_N = (int)1e5 + 5;
const int MAX_M = (int)2e5 + 5;
const int MAX_Q = (int)1e5 + 5;
const int S = 300;
const int INF = 1e9;

vector <int> g[MAX_N];

vector <int> busy[MAX_Q];
int t[MAX_Q];
int n, m, q;

void check(vector <pii> &vec) {
	for (int i = 0; i + 1 < szof(vec); i++) {
		assert(vec[i].sc >= vec[i + 1].sc);
	}
}

struct Full_Solution {
	vector <pii> far[MAX_N]; // vertex dist
	// far[i][0] >= far[i][1] >= far[i][2] >= by distance
	void precalc() {
		for (int i = 1; i <= n; i++) {
			far[i].pb({i, 0});
		}
		vector <int> visited(MAX_N, -1);
		int vis_id = 1;
		for (int i = 1; i <= n; i++) {
			for (int to : g[i]) {
				vis_id++;
				vector <pii> vec;
				int l = 0, r = 0;
				while (l < szof(far[i]) && r < szof(far[to]) && szof(vec) < S) {
					if (visited[far[i][l].fr] == vis_id) {
						l++;
						continue;
					}
					if (visited[far[to][r].fr] == vis_id) {
						r++;
						continue;
					}
					if (far[i][l].sc + 1 > far[to][r].sc) {
						vec.pb({far[i][l].fr, far[i][l].sc + 1});
						visited[far[i][l].fr] = vis_id;
						l++;
					} else {
						vec.pb(far[to][r]);
						visited[far[to][r].fr] = vis_id;
						r++;
					}
				}
				if (szof(vec) < S) {
					while (l < szof(far[i]) && szof(vec) < S) {
						if (visited[far[i][l].fr] == vis_id) {
							l++;
							continue;
						}
						visited[far[i][l].fr] = vis_id;
						vec.pb({far[i][l].fr, far[i][l].sc + 1});
						l++;
					}
					while (r < szof(far[to]) && szof(vec) < S) {
						if (visited[far[to][r].fr] == vis_id) {
							r++;
							continue;
						}
						visited[far[to][r].fr] = vis_id;
						vec.pb(far[to][r]);
						r++;
					}
				}
				far[to] = vec;
			}
		}
	}
	void run() {
		vector <int> is_busy(MAX_N, false);
		vector <int> dp(MAX_N);
		vector <int> busy_id(MAX_N, -1);
		precalc();
		for (int i = 1; i <= q; i++) {
			for (int el : busy[i]) {
				busy_id[el] = i;
			}
			if (szof(busy[i]) >= S) {
				for (int j = 1; j <= n; j++) {
					dp[j] = -INF;
				}
				dp[t[i]] = 0;
				int ans = -1;
				for (int v = n; v >= 1; v--) {
					for (int to : g[v]) {
						if (dp[to] != -INF) {
							chmax(dp[v], 1 + dp[to]);
						}
					}
					if (busy_id[v] != i) {
						chmax(ans, dp[v]);
					}
				}
				cout << ans << endl;				
			}
			else { // szof(busy[i]) < S
				int ans = -1;
				for (auto [v, dist] : far[t[i]]) {
					if (busy_id[v] != i) {
						ans = dist;
						break;
					}
				}
				cout << ans << endl;
			}
		}
	}
};

signed main() {
	fastInp;
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		int from, to;
		cin >> from >> to;
		g[from].pb(to);
	}
	for (int i = 1, sz; i <= q; i++) {
		cin >> t[i] >> sz;
		for (int j = 1; j <= sz; j++) {
			int v;
			cin >> v;
			busy[i].pb(v);
		}
	}
	Full_Solution T;
	T.run();
}

/*
5 6 3
1 2
2 4
3 4
1 3
3 5
4 5
5 2 2 3
4 1 1
2 3 1 4 5

*/

Compilation message (stderr)

bitaro.cpp: In member function 'void Full_Solution::run()':
bitaro.cpp:120:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |     for (auto [v, dist] : far[t[i]]) {
      |               ^

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