Submission #58437

#TimeUsernameProblemLanguageResultExecution timeMemory
58437ksun48Bitaro’s Party (JOI18_bitaro)C++14
14 / 100
2085 ms36836 KiB
#include <bits/stdc++.h> using namespace std; const int SIZE = 20; int main(){ cin.sync_with_stdio(0); cin.tie(0); int n, m, q; cin >> n >> m >> q; vector<int> edges[n]; for(int i = 0; i < m; i++){ int s, e; cin >> s >> e; s--; e--; edges[e].push_back(s); } vector<pair<int,int> > best[n]; vector<int> seen(n, 0); for(int b = 0; b < n; b++){ vector<pair<int,int> > cand; cand.push_back({0,b}); for(int a : edges[b]){ for(pair<int,int> x : best[a]){ cand.push_back({x.first + 1, x.second}); } } sort(cand.begin(), cand.end()); reverse(cand.begin(), cand.end()); for(pair<int,int> x : cand){ if(seen[x.second]) continue; if(best[b].size() > SIZE) break; seen[x.second] = 1; best[b].push_back(x); } for(pair<int,int> x : cand){ seen[x.second] = 0; } } vector<int> attend(n, 1); vector<int> dp(n, -1); for(int qq = 0; qq < q; qq++){ int town, y; cin >> town >> y; town--; vector<int> bad(y); for(int i = 0; i < y; i++){ cin >> bad[i]; bad[i]--; attend[bad[i]] = 0; } if(y < SIZE){ int ans = -1; for(pair<int,int> x : best[town]){ if(attend[x.second]){ ans = x.first; break; } } cout << ans << '\n'; } else { for(int b = 0; b < n; b++){ dp[b] = -1; } for(int b = 0; b < n; b++){ if(attend[b]){ dp[b] = 0; } for(int a : edges[b]){ if(dp[a] >= 0){ dp[b] = max(dp[b], dp[a] + 1); } } } cout << dp[town] << '\n'; } for(int i = 0; i < y; i++){ attend[bad[i]] = 1; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...