제출 #410607

#제출 시각아이디문제언어결과실행 시간메모리
410607koioi.org-namnamseoBitaro’s Party (JOI18_bitaro)C++17
0 / 100
12 ms5452 KiB
#include <iostream> #include <vector> #include <set> #include <queue> #include <utility> #include <algorithm> using namespace std; using pp=pair<int, int>; const int maxn = int(1e5) + 10; const int B = 300; int n, m, q; vector<int> re[maxn]; vector<pp> prec[maxn]; int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m >> q; for (int i=1; i<=m; ++i) { int s, e; cin >> s >> e; re[e].push_back(s); } for (int i=1; i<=n; ++i) { static priority_queue<pp> pq; { priority_queue<pp> tmp; swap(pq, tmp); } pq.emplace(0, i); static int bi[maxn]; for (int j:re[i]) { bi[j] = 0; pq.emplace(prec[j][0].first+1, j); } set<int> seen; for (int t=0; t<B && pq.size(); ++t) { auto [v, j] = pq.top(); pq.pop(); if (j == i) { prec[i].emplace_back(0, i); continue; } int &ji = bi[j]; if (seen.count(prec[j][ji].second)) { --t; } else { prec[i].emplace_back(v, prec[j][ji].second); seen.insert(prec[j][ji].second); } ++ji; if (ji < int(prec[j].size())) { pq.emplace(prec[j][ji].first+1, j); } } } for (;q--;) { int dest, igs; cin >> dest >> igs; static int ign[maxn]; for (int i=0; i<igs; ++i) cin >> ign[i]; sort(ign, ign+igs); ign[igs] = 0; if (igs < B) { bool found = 0; for (auto [dist, from]:prec[dest]) { if ((*lower_bound(ign, ign+igs, from)) != from) { cout << dist << '\n'; found = 1; break; } } if (!found) { cout << "-1\n"; } continue; } static queue<int> Q; Q.push(dest); static int qd[maxn]; fill(qd+1, qd+dest+1, 0); int ans = -1; while (Q.size()) { int x = Q.front(); Q.pop(); if ((*lower_bound(ign, ign+igs, x)) != x) { ans = qd[x]; } for (int y:re[x]) if (!qd[y]) { qd[y] = qd[x] + 1; Q.push(y); } } cout << ans << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...