제출 #531909

#제출 시각아이디문제언어결과실행 시간메모리
531909Alex_tz307Bitaro’s Party (JOI18_bitaro)C++17
7 / 100
2085 ms10356 KiB
#include <bits/stdc++.h> using namespace std; const int kN = 1e5; const int bucket = 50; vector<int> gt[1 + kN]; vector<pair<int, int>> paths[1 + kN]; int ptr[1 + kN], vis[1 + kN], b[kN], dp[1 + kN]; bitset<1 + kN> blocked; void testCase() { int n, m, q; cin >> n >> m >> q; for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; gt[v].emplace_back(u); } for (int u = 1; u <= n; ++u) { priority_queue<tuple<int, int, int>> pq; pq.emplace(-1, u, -1); for (int v : gt[u]) { if (!paths[v].empty()) { ptr[v] = 0; pq.emplace(paths[v][0].first, paths[v][0].second, v); } } while (!pq.empty()) { int len, node, v; tie(len, node, v) = pq.top(); pq.pop(); if (vis[node] != u) { paths[u].emplace_back(len + 1, node); vis[node] = u; } if (v == -1) { continue; } ptr[v] += 1; if (ptr[v] < (int)paths[v].size()) { pq.emplace(paths[v][ptr[v]].first, paths[v][ptr[v]].second, v); } } } for (int i = 0; i < q; ++i) { int s, m; cin >> s >> m; for (int j = 0; j < m; ++j) { cin >> b[j]; blocked[b[j]] = true; } if (bucket <= m) { for (int u = 1; u <= n; ++u) { if (blocked[u]) { dp[u] = -1; } else { dp[u] = 0; } for (int v : gt[u]) { if (dp[v] != -1 && dp[u] < dp[v] + 1) { dp[u] = dp[v] + 1; } } } cout << dp[s] << '\n'; } else { int ans = -1; for (auto it : paths[s]) { if (!blocked[it.second]) { ans = it.first; break; } } cout << ans << '\n'; } for (int j = 0; j < m; ++j) { blocked[b[j]] = false; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int tests = 1; for (int tc = 0; tc < tests; ++tc) { testCase(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...