| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1245345 | enjeeeff | Bitaro’s Party (JOI18_bitaro) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
typedef long long ll;
#define vec vector
using namespace std;
const ll bl = 100;
ll dp[1e5 + 1];
ll busyWhole[1e5 + 1];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
ll n, m, q;
cin >> n >> m >> q;
ll i;
vec<vec<long long> > rev(n + 1);
vec<vec<pair<ll, ll> > > topPaths(n + 1);
for (i = 0; i < m; i++) {
ll a, b;
cin >> a >> b;
rev[b].push_back(a);
}
ll j;
vec<ll> busyList;
for (i = 1; i <= n; i++) {
priority_queue<tuple<ll, ll, ll>, vec<tuple<ll, ll, ll> > > qu;
for (j = 0; j < rev[i].size(); j++)
qu.emplace(topPaths[rev[i][j]][0].first, j, 0);
while (qu.size() && topPaths[i].size() < bl) {
auto [length, id, ord] = qu.top();
auto &revTops = topPaths[rev[i][id]];
qu.pop();
if (!busyWhole[revTops[ord].second]) {
busyList.push_back(revTops[ord].second);
busyWhole[revTops[ord].second] = 1;
topPaths[i].emplace_back(length + 1, revTops[ord].second);
}
if (ord + 1 < revTops.size())
qu.emplace(revTops[ord + 1].first, id, ord + 1);
}
topPaths[i].push_back({0, i});
for (auto &el : busyList)
busyWhole[el] = 0;
busyList.clear();
}
while (q--) {
ll t, y;
cin >> t >> y;
for (i = 0; i < y; i++) {
ll b;
cin >> b;
busyList.push_back(b);
busyWhole[b] = 1;
}
if (t >= bl) {
ranges::fill(dp, -1);
for (i = 1; i <= n; i++) {
if (!busyWhole[i]) dp[i] = 0;
for (auto &a : rev[i])
if (dp[a] != -1) dp[i] = max(dp[i], dp[a] + 1);
}
cout << dp[t] << '\n';
}
else {
for (i = 0; i < topPaths[t].size() && busyWhole[topPaths[t][i].second]; i++);
cout << (i < topPaths[t].size() ? topPaths[t][i].first : -1) << '\n';
}
for (auto &el : busyList)
busyWhole[el] = 0;
busyList.clear();
}
}