제출 #928435

#제출 시각아이디문제언어결과실행 시간메모리
928435myst6Bitaro’s Party (JOI18_bitaro)C++14
7 / 100
2047 ms5140 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 100'000; const int B = 320; int main() { cin.tie(0)->sync_with_stdio(0); int N, M, Q; cin >> N >> M >> Q; vector<vector<int>> in(N); for (int i=0; i<M; i++) { int S, E; cin >> S >> E; S--, E--; in[E].push_back(S); } vector<vector<pair<int,int>>> dp(N); for (int i=0; i<N; i++) { set<pair<int,int>> S; for (int u : in[i]) { for (pair<int,int> p : dp[u]) { S.insert({p.first + 1, p.second}); } } S.insert({0, i}); int k = B; for (auto it = S.rbegin(); it != S.rend() && k > 0; ++it, --k) { dp[i].push_back(*it); } } for (int j=0; j<Q; j++) { int T, Y; cin >> T >> Y; T--; set<int> C; for (int i=0; i<Y; i++) { int c; cin >> c; C.insert(c-1); } if (Y < B) { bool ans = false; for (pair<int,int> p : dp[T]) { if (C.count(p.second) == 0) { cout << p.first << "\n"; ans = true; break; } } if (!ans) { cout << "-1\n"; } } else { vector<int> dp2(N, -1); dp2[T] = 0; for (int i=T; i>=0; i--) { if (dp2[i] == -1) continue; for (int u : in[i]) { dp2[u] = max(dp2[u], dp2[i] + 1); } } int ans = -1; for (int i=0; i<=T; i++) { if (dp2[i] > ans && C.count(i) == 0) ans = dp2[i]; } cout << ans << "\n"; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...