Submission #1224922

#TimeUsernameProblemLanguageResultExecution timeMemory
1224922totoroBitaro’s Party (JOI18_bitaro)C++20
14 / 100
2047 ms146100 KiB
#include <iostream> #include <queue> #include <random> #include <set> #include <utility> #include <vector> #pragma GCC target("avx2") const size_t SQRT = 160; std::vector<std::pair<int, int>> merge_sqrt(std::vector<std::pair<int, int>>& a, std::vector<std::pair<int, int>>& b, std::vector<int>& seenby) { int key = std::random_device()(); std::vector<std::pair<int, int>> res; res.reserve(SQRT + 1); int ap, bp; // pointers to current elements to consider ap = bp = 0; while (res.size() < SQRT + 1) { if (ap < a.size() && seenby[a[ap].second] == key) { ++ap; } else if (bp < b.size() && seenby[b[bp].second] == key) { ++bp; } else if (ap == a.size()) { if (bp == b.size()) return res; seenby[b[bp].second] = key; res.push_back(b[bp++]); } else if (bp == b.size()) { seenby[a[ap].second] = key; res.push_back(a[ap++]); } else if (seenby[b[bp].second] == key) { ++bp; } else if (a[ap] > b[bp]) { seenby[a[ap].second] = key; res.push_back(a[ap++]); } else { seenby[b[bp].second] = key; res.push_back(b[bp++]); } } return res; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m, q; std::cin >> n >> m >> q; std::vector<std::vector<int>> upadj(n), downadj(n); for (int i = 0; i < m; ++i) { int u, v; std::cin >> u >> v; --u, --v; upadj[v].push_back(u); downadj[u].push_back(v); } std::vector<std::vector<std::pair<int, int>>> furthest_ancestors(n); // (dist, index) std::vector<int> mergerseen(n); auto dfsup = [&](int node, auto dfs) -> void { if (!furthest_ancestors[node].empty()) return; furthest_ancestors[node] = {{-1, node}}; for (int to : upadj[node]) { dfs(to, dfs); furthest_ancestors[node] = merge_sqrt(furthest_ancestors[node], furthest_ancestors[to], mergerseen); } for (auto& [dist, index] : furthest_ancestors[node]) { ++dist; } }; for (int i = 0; i < n; ++i) dfsup(i, dfsup); std::vector<int> is_removed(n); while (q--) { int partytown, removed; std::cin >> partytown >> removed; --partytown; std::vector<int> which_removed(removed); for (int& i : which_removed) std::cin >> i, --i; for (int i : which_removed) is_removed[i] = true; if (removed > SQRT) { // solve in one big dfs std::vector<int> distance(n, -1); distance[partytown] = 0; auto dfsdown = [&](int node, auto dfs) -> void { if (distance[node] != -1) return; int max = -1e9; for (int to : downadj[node]) { dfs(to, dfs); max = std::max(max, distance[to]); } distance[node] = max + 1; }; int max = -1; for (int i = 0; i < n; ++i) { if (is_removed[i]) continue; dfsdown(i, dfsdown); max = std::max(max, distance[i]); } std::cout << max << '\n'; } else { // use preprocess int ans = -1; for (auto [dist, node] : furthest_ancestors[partytown]) { if (is_removed[node]) continue; ans = dist; break; } std::cout << ans << '\n'; } for (int i : which_removed) is_removed[i] = false; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...