Submission #471586

#TimeUsernameProblemLanguageResultExecution timeMemory
471586RainbowbunnyBitaro’s Party (JOI18_bitaro)C++17
0 / 100
16 ms8404 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; const int SQRT = 300; int n, m, q, c; int dp[MAXN], a[MAXN]; bool Mark[MAXN]; vector <int> Adj[MAXN]; vector <pair <int, int> > Dist[MAXN]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m >> q; for(int i = 1; i <= m; i++) { int u, v; cin >> u >> v; Adj[v].push_back(u); } for(int i = 1; i <= n; i++) { Dist[i].emplace_back(0, i); for(auto x : Adj[i]) { c = 0; vector <pair <int, int> > tmp; int pt0 = 0, pt1 = 0; while(pt0 < (int)Dist[i].size() and pt1 < (int)Dist[x].size() and Dist[i].size() < SQRT) { if(Dist[i][pt0].first > Dist[x][pt1].first + 1) { if(!Mark[Dist[i][pt0].second]) { Mark[Dist[i][pt0].second] = 1; a[c] = Dist[i][pt0].second; c++; tmp.emplace_back(Dist[i][pt0]); } pt0++; } else { if(!Mark[Dist[x][pt1].second]) { Mark[Dist[x][pt1].second] = 1; a[c] = Dist[x][pt1].second; c++; tmp.emplace_back(Dist[x][pt1].first + 1, Dist[x][pt1].second); } pt1++; } } while(pt0 < (int)Dist[i].size() and tmp.size() < SQRT) { if(!Mark[Dist[i][pt0].second]) { Mark[Dist[i][pt0].second] = 1; a[c] = Dist[i][pt0].second; c++; tmp.emplace_back(Dist[i][pt0]); } pt0++; } while(pt1 < (int)Dist[x].size() and tmp.size() < SQRT) { if(!Mark[Dist[x][pt1].second]) { Mark[Dist[x][pt1].second] = 1; a[c] = Dist[x][pt1].second; c++; tmp.emplace_back(Dist[x][pt1].first + 1, Dist[x][pt1].second); } pt1++; } swap(tmp, Dist[i]); for(int j = 0; j < c; j++) { Mark[a[j]] = false; } } } for(int i = 1; i <= n; i++) { assert(Mark[i] == false); } while(q--) { int t, sz; cin >> t >> sz; vector <int> tmp(sz); for(auto &x : tmp) { cin >> x; Mark[x] = true; } bool ok = false; for(int i = 0; i < (int)Dist[t].size(); i++) { if(!Mark[Dist[t][i].second]) { ok = true; cout << Dist[t][i].first << '\n'; break; } } if(!ok) { int ans = -1; for(int i = 1; i <= n; i++) { dp[i] = -1e9; } dp[t] = 0; for(int i = t; i >= 1; i--) { for(auto x : Adj[i]) { dp[x] = max(dp[x], dp[i] + 1); } if(!Mark[i]) { ans = max(ans, dp[i]); } } cout << ans << '\n'; } for(auto x : tmp) { Mark[x] = false; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...