제출 #769651

#제출 시각아이디문제언어결과실행 시간메모리
769651PurpleCrayonBitaro’s Party (JOI18_bitaro)C++17
14 / 100
442 ms210548 KiB
#include <bits/stdc++.h> using namespace std; #define sz(v) int(v.size()) #define ar array typedef long long ll; const int N = 1e5+10, MOD = 998244353; const int B = 200; int n, m, q; vector<int> adj[N]; vector<pair<int, int>> best[N]; // sorted from biggest to smallest void merge_into(vector<pair<int, int>>& one, const vector<pair<int, int>>& two) { vector<pair<int, int>> ans; int p1 = 0, p2 = 0; auto move_one = [&]() { ans.push_back(one[p1++]); }; auto move_two = [&]() { ans.push_back(two[p2++]); }; while (sz(ans) < B && (p1 < sz(one) || p2 < sz(two))) { if (p1 == sz(one)) move_two(); else if (p2 == sz(two)) move_one(); else if (one[p1] > two[p2]) move_one(); else move_two(); } one.clear(); for (auto x : ans) one.push_back(x); } int dp[N]; bool bad[N]; void solve() { cin >> n >> m >> q; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b, --a, --b; adj[b].push_back(a); } for (int i = 0; i < n; i++) { for (int nxt : adj[i]) { merge_into(best[i], best[nxt]); } for (auto& [x, c] : best[i]) x++; best[i].emplace_back(0, i); while (sz(best[i]) > B) best[i].pop_back(); } while (q--) { int c, k; cin >> c >> k, --c; if (k < B) { vector<int> v(k); for (auto& x : v) cin >> x, --x; for (int x : v) bad[x] = 1; int ans = -1; for (auto [x, i] : best[c]) if (!bad[i]) { ans = x; break; } for (int x : v) bad[x] = 0; cout << ans << '\n'; } else { memset(dp, 0, sizeof(dp)); for (int i = 0; i < k; i++) { int x; cin >> x, --x; dp[x] = -MOD; } for (int i = 0; i < n; i++) { for (int nxt : adj[i]) { dp[i] = max(dp[i], dp[nxt] + 1); } } cout << (dp[c] < 0 ? -1 : dp[c]) << '\n'; } } } int main() { ios::sync_with_stdio(false); cin.tie(0); int T = 1; // cin >> T; while (T--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...