제출 #531903

#제출 시각아이디문제언어결과실행 시간메모리
531903Alex_tz307Bitaro’s Party (JOI18_bitaro)C++17
14 / 100
2096 ms110928 KiB
#include <bits/stdc++.h> using namespace std; const int kN = 1e5; const int bucket = 64; vector<int> gt[1 + kN]; vector<pair<int, int>> paths[1 + kN]; int vis[1 + kN], b[kN], dp[1 + kN]; bitset<1 + kN> blocked; void maxSelf(int &x, int y) { if (x < y) { x = y; } } 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) { vector<pair<int, int>> aux{{0, u}}; for (int v : gt[u]) { for (auto it : paths[v]) { aux.emplace_back(it.first + 1, it.second); } } sort(aux.begin(), aux.end(), greater<pair<int, int>>()); for (auto it : aux) { if (vis[it.second] != u) { paths[u].emplace_back(it); vis[it.second] = u; } } while ((int)paths[u].size() > bucket) { paths[u].pop_back(); } } 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) { maxSelf(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...