Submission #868552

#TimeUsernameProblemLanguageResultExecution timeMemory
868552lolismekBitaro’s Party (JOI18_bitaro)C++14
100 / 100
1242 ms324228 KiB
#include <algorithm> #include <iostream> #include <vector> #define pii pair <int, int> using namespace std; const int NMAX = 100000; const int B = 250; vector <int> adj[NMAX + 1]; vector <pii> t[NMAX + 1]; int from[NMAX + 1]; int dist[NMAX + 1]; bool no[NMAX + 1]; int main(){ int n, m, q; cin >> n >> m >> q; for(int i = 1; i <= m; i++){ int a, b; cin >> a >> b; adj[b].push_back(a); } for(int i = 1; i <= n; i++){ vector <int> curr; for(int vec : adj[i]){ for(pii x : t[vec]){ if(from[x.second] == i){ dist[x.second] = max(dist[x.second], x.first + 1); }else{ from[x.second] = i; dist[x.second] = x.first + 1; curr.push_back(x.second); } } } t[i].push_back({0, i}); for(int x : curr){ t[i].push_back({dist[x], x}); } sort(t[i].begin(), t[i].end(), greater <pii>()); if((int)t[i].size() > B){ t[i].erase(t[i].begin() + B, t[i].end()); } } while(q--){ int node, nr; cin >> node >> nr; vector <int> bad; for(int i = 1; i <= nr; i++){ int x; cin >> x; bad.push_back(x); no[x] = true; } int ans = -1; if((int)bad.size() > B){ vector <int> dp(n + 1, -1); dp[node] = 0; for(int i = node; i >= 1; i--){ if(dp[i] != -1){ if(!no[i]){ ans = max(ans, dp[i]); } for(int vec : adj[i]){ dp[vec] = max(dp[vec], dp[i] + 1); } } } }else{ for(pii x : t[node]){ if(!no[x.second]){ ans = x.first; break; } } } cout << ans << '\n'; for(int x : bad){ no[x] = false; } } return 0; } /* 5 6 3 1 2 2 4 3 4 1 3 3 5 4 5 4 1 1 5 2 2 3 2 3 1 4 5 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...