제출 #1215024

#제출 시각아이디문제언어결과실행 시간메모리
1215024vaneaBitaro’s Party (JOI18_bitaro)C++20
100 / 100
1083 ms211140 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int SQ = 150; 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++) { vector<int> add_idx; paths[i].push_back({0, i}); for(auto it : adj[i]) { for(auto [dist, idx] : paths[it]) { if(from[idx] == -1) { from[idx] = dist+1; add_idx.push_back(idx); } else { from[idx] = max(from[idx], dist+1); } } } for(auto it : add_idx) paths[i].push_back({from[it], it}); sort(paths[i].rbegin(), paths[i].rend()); while(paths[i].size() > SQ) paths[i].pop_back(); for(auto it : add_idx) from[it] = -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> dist(t+1, -1); dist[t] = 0; for(int i = t; i >= 1; i--) { if(dist[i] == -1) continue; if(!blocked[i]) ans = max(ans, dist[i]); for(auto it : adj[i]) { dist[it] = max(dist[it], dist[i]+1); } } } else { for(auto [dist, idx] : paths[t]) { if(blocked[idx]) continue; ans = max(ans, dist); } } cout << ans << '\n'; for(auto it : now) blocked[it] = false; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...