제출 #1227909

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227909		wedonttalkanymore	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1273 ms	411788 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

//#define int long long
#define pii pair <int, int>
#define fi first
#define se second

const ll N = 1e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 320;

int n, m, q;
int vst[N], val[N];
bool rem[N];
vector <int> adj[N];
vector <pii> path[N];

bool cmp(pii a, pii b) {
	return a.se > b.se;
}

ll topo(int u) {
	vector <ll> dp(n + 1, 0);
	for (int i = 1; i <= n; i++) {
		if (rem[i]) dp[i] = -inf;
	}
	for (int j = 1; j <= u; j++) {
		for (auto v : adj[j]) {
			dp[j] = max(dp[j], dp[v] + 1);
		}
	}
	return dp[u];
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		adj[v].push_back(u);
	}
	for (int u = 1; u <= n; u++) {
		vector <int> tmp;
		vst[u] = u;
		val[u] = 0;  
		tmp.emplace_back(u);
		for (auto v : adj[u]) {
			for (auto p : path[v]) {
				if (vst[p.fi] != u) {
					vst[p.fi] = u;
					val[p.fi] = p.se + 1;
					tmp.push_back(p.fi);
				}
				else {
					val[p.fi] = max(val[p.fi], p.se + 1);
				}
			}
		}
		for (auto i : tmp) path[u].emplace_back(i, val[i]);
		sort(path[u].begin(), path[u].end(), cmp);
		int x = path[u].size();
		while(x > block) {
			x--;
			path[u].pop_back();
		}
	}
//	for (int i = 1; i <= n; i++) {
//		for (auto v : path[i]) cout << i << ' ' << v.fi << ' ' << v.se << '\n';
//	}
	while(q-- > 0) {
		int t, sz;
		cin >> t >> sz;
		vector <int> tmp(sz + 1, 0);
		for (int i = 1; i <= sz; i++) {
			cin >> tmp[i];
			rem[tmp[i]] = true;
		}
		ll ans = -1;
		if (sz >= block) {
			ans = topo(t);
		}
		else {
			for (auto i : path[t]) {
				if (!rem[i.fi]) {
					ans = i.se;
					break;
				}
			}
		}
		for (int i = 1; i <= sz; i++) {
			rem[tmp[i]] = false;
		}
		if (ans > -1e17) cout << ans << '\n';
		else cout << -1 << '\n';
	}
	return 0;
}

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