Submission #1085321

#TimeUsernameProblemLanguageResultExecution timeMemory
1085321eysbutnoBitaro’s Party (JOI18_bitaro)C++17
100 / 100
1592 ms69060 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = array<int, 2>; #define all(x) begin(x), end(x) #define sz(x) (int) (x).size() constexpr int B = 45; int main() { cin.tie(0) -> sync_with_stdio(0); int n, m, q; cin >> n >> m >> q; vector<vector<int>> adj(n); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; --u, --v; adj[u].push_back(v); } vector<int> mp(n, -1); vector<vector<pii>> best(n); const auto merge = [&](int from, int to) -> void { vector<int> seen; for (auto [node, dist] : best[from]) { mp[node] = max(mp[node], dist + 1); seen.push_back(node); } for (auto [node, dist] : best[to]) { mp[node] = max(mp[node], dist); seen.push_back(node); } best[to].clear(); for (int x : seen) { if (mp[x] == -1) { continue; } best[to].push_back({x, mp[x]}); mp[x] = -1; } sort(all(best[to]), [&](auto &x, auto &y) -> bool { return x[1] > y[1]; }); if (sz(best[to]) > B) { best[to].resize(B); } }; for (int u = 0; u < n; u++) { if (sz(best[u]) < B) { best[u].push_back({u, 0}); } for (int v : adj[u]) { merge(u, v); } } const auto check = [&](int t, const set<int> &bad) -> int { for (auto [node, dist] : best[t]) { if (!bad.count(node)) { return dist; } } return -1; }; const auto brute_force = [&](int t, const set<int> &bad) -> int { vector<int> opt(n, -1); for (int u = 0; u <= t; u++) { if (!bad.count(u)) { opt[u] = max(0, opt[u]); } for (int v : adj[u]) { if (opt[u] != -1) { opt[v] = max(opt[v], opt[u] + 1); } } } return opt[t]; }; while (q--) { int t, y; cin >> t >> y; --t; set<int> bad; for (int i = 0; i < y; i++) { int x; cin >> x; bad.insert(--x); } if (y >= B) { cout << brute_force(t, bad) << "\n"; } else { cout << check(t, bad) << "\n"; } } /* for (int i = 0; i < n; i++) { cout << "node " << i + 1 << "\n"; for (auto [node, dist] : best[i]) { cout << node + 1 << " " << dist << "\n"; } } */ }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...