제출 #963198

#제출 시각아이디문제언어결과실행 시간메모리
963198TimAniBitaro’s Party (JOI18_bitaro)C++17
0 / 100
1 ms860 KiB
//start-time: 2024-04-14 19:39:32 #include <bits/stdc++.h> using namespace std; using ll = long long; void solve(){ int n, m, q; cin >> n >> m >> q; vector<vector<int>> g(n); vector<vector<int>> gR(n); for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; u--; v--; g[u].push_back(v); gR[v].push_back(u); } vector<int> vis(n), topo; auto dfs = [&](int u, auto&&dfs) -> void { vis[u] = 1; for(auto v : g[u]){ if(!vis[v]){ dfs(v, dfs); } } vis[u] = 2; topo.push_back(u); }; dfs(0, dfs); reverse(topo.begin(), topo.end()); vector<multiset<array<int, 2>>> dp(n); for(auto el : topo){ dp[el].insert({0, el}); } const int w = round(sqrt(100'000)); for(auto u : topo){ for(auto v : gR[u]){ for(auto [v, i] : dp[v]){ dp[u].insert({v + 1, i}); if(dp[u].size() > w){ dp[u].erase(dp[u].begin()); } } } } for(int i = 0; i < q; i++){ int u, num; cin >> u >> num; u--; multiset<array<int, 2>> ms = dp[u]; vector<int> c(100'000 + 1); for(int j = 0; j < num; j++){ int a; cin >> a; c[--a] = 1; } int ans = 0; for(auto [v, i] : ms){ if(!c[i]){ ans = max(ans, v); } } cout << ans << endl; } } int main() { cin.tie(0)->sync_with_stdio(0); int T = 1; //cin >> T; while(T--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...