제출 #426473

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
426473		milleniumEeee	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	448 ms	24304 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
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 INF = 1e9;

vector <int> g[MAX_N];

vector <int> busy[MAX_Q];
int t[MAX_Q];

int dp[1005][1005];
int is_busy[MAX_Q], used_id = 0;

signed main() {
	fastInp;
	int n, m, q;
	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);
		}
	}
	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;
	}
}

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

*/

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