Submission #1215017

#TimeUsernameProblemLanguageResultExecution timeMemory
1215017vaneaBitaro’s Party (JOI18_bitaro)C++20
100 / 100
778 ms143380 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int SQ = 100; const int mxN = 1e5+10; vector<int> adj[mxN]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m, q; cin >> n >> m >> q; for(int i = 0; i < m; i++) { int a, b; cin >> a >> b; adj[b].push_back(a); } vector<vector<array<int, 2>>> paths(n+1); vector<int> from(n+1, -1); for(int i = 1; i <= n; i++) { paths[i].push_back({0, i}); vector<int> from_idx; for(auto it : adj[i]) { for(auto [dist, idx] : paths[it]) { if(from[idx] == -1) { from_idx.push_back(idx); from[idx] = dist+1; } else { from[idx] = max(from[idx], dist+1); } } } for(int j : from_idx) paths[i].push_back({from[j], j}); sort(paths[i].rbegin(), paths[i].rend()); while(paths[i].size() > SQ) paths[i].pop_back(); for(int j : from_idx) from[j] = -1; } vector<bool> blocked(n+1); while(q--) { int t, y; cin >> t >> y; vector<int> now(y); for(int i = 0; i < y; i++) { cin >> now[i]; blocked[now[i]] = true; } int ans = -1; if(y >= SQ) { vector<int> dp(t+1, -1); dp[t] = 0; for(int i = t; i >= 0; i--) { if(dp[i] == -1) continue; if(!blocked[i]) ans = max(ans, dp[i]); for(auto it : adj[i]) { dp[it] = max(dp[it], dp[i]+1); } } } else { for(auto [dist, idx] : paths[t]) { if(blocked[idx]) continue; ans = dist; break; } } cout << ans << '\n'; for(auto it : now) blocked[it] = false; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...