제출 #1085312

#제출 시각아이디문제언어결과실행 시간메모리
1085312eysbutnoBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2062 ms118872 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 = 100; int main() { cin.tie(0) -> sync_with_stdio(0); int n, m, q; cin >> n >> m >> q; vector<vector<int>> adj(n); vector<int> deg(n); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; --u, --v; adj[u].push_back(v); ++deg[v]; } vector<vector<pii>> best(n); auto cur = deg; queue<int> top; for (int i = 0; i < n; i++) { if (!cur[i]) { top.push(i); } } const auto merge = [&](int from, int to) -> void { map<int, int> mp; for (auto [node, dist] : best[from]) { mp[node] = max(mp[node], dist + 1); } for (auto [node, dist] : best[to]) { mp[node] = max(mp[node], dist); } best[to].clear(); for (auto [node, dist] : mp) { best[to].push_back({node, dist}); } sort(all(best[to]), [&](auto &x, auto &y) -> bool { return x[1] > y[1]; }); if (sz(best[to]) > B) { best[to].resize(B); } }; while (!top.empty()) { int u = top.front(); top.pop(); if (sz(best[u]) < B) { best[u].push_back({u, 0}); } for (int v : adj[u]) { merge(u, v); if (!(--cur[v])) { top.push(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 { queue<int> q; auto cur = deg; vector<int> best(n, -1); for (int i = 0; i < n; i++) { if (!cur[i]) { q.push(i); } } while (!q.empty()) { int u = q.front(); q.pop(); if (!bad.count(u)) { best[u] = max(0, best[u]); } if (u == t) { break; } for (int v : adj[u]) { if (best[u] != -1) { best[v] = max(best[v], best[u] + 1); } if (!--cur[v]) { q.push(v); } } } return best[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...