Submission #426523

#	Time	Username	Problem	Language	Result	Execution time	Memory
426523		milleniumEeee	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	1402 ms	250092 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;

struct Subtask1_Solve { // O(M * N) time complexity
	int dp[1005][1005];
	int is_busy[1005], used_id = 0;	
	void run() {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
			dp[i][j] = -INF;
				if (i == j) {
					dp[i][j] = 0;
				}
			}
		}
		for (int i = n; i >= 1; i--) {
			for (int to : g[i]) {
				for (int j = 1; j <= n; j++) {
					if (dp[to][j] == INF) {
						continue;
					} else {
						chmax(dp[i][j], 1 + dp[to][j]);
					}
				}
			}
		}
		for (int i = 1; i <= q; i++) {
			used_id++;
			for (int el : busy[i]) {
				is_busy[el] = used_id;
			}
			int mx = -1;
			for (int j = 1; j <= n; j++) {
				if (is_busy[j] != used_id) {
					chmax(mx, dp[j][t[i]]);
				}
			}
			cout << mx << endl;
		}
	}
};

struct Subtask2_Solve { // O(M) time complexity for 1 query
	int dp[MAX_N];
	void run() {
		fill(dp, dp + MAX_N, -INF);
		dp[t[1]] = 0; 
		int ans = -1;
		for (int i = n; i >= 1; i--) {
			for (int to : g[i]) {
				if (dp[to] != -INF) {
					chmax(dp[i], 1 + dp[to]);
				}
			}
			if (binary_search(all(busy[1]), i) == false) {
				chmax(ans, dp[i]);
			}
		}
		cout << ans << endl;
	}
};

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});
		}
		for (int i = 1; i <= n; i++) {
			for (int to : g[i]) {
				vector <pii> vec;
				int l = 0, r = 0;
				while (l < szof(far[i]) && r < szof(far[to]) && szof(vec) < S) {
					if (far[i][l].sc + 1 > far[to][r].sc) {
						vec.pb({far[i][l].fr, far[i][l].sc + 1});
						l++;
					} else {
						vec.pb(far[to][r]);
						r++;
					}
				}
				if (szof(vec) < S) {
					while (l < szof(far[i]) && szof(vec) < S) {
						vec.pb({far[i][l].fr, far[i][l].sc + 1});
						l++;
					}
					while (r < szof(far[to]) && szof(vec) < S) {
						vec.pb(far[to][r]);
						r++;
					}
				}
				assert(szof(vec) <= S);
				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:151:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  151 |     for (auto [v, dist] : far[t[i]]) {
      |               ^

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