Submission #423224

#TimeUsernameProblemLanguageResultExecution timeMemory
423224snasibov05Bitaro’s Party (JOI18_bitaro)C++14
7 / 100
2059 ms413416 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; #define pb push_back #define pii pair<int, int> #define f first #define s second #define oo 1000000000 const int b = 320; vector<vector<int>> ed; vector<vector<pii>> mx; vector<int> dist; vector<int> dp; vector<bool> busy; void dfs(int v){ for (auto to : ed[v]){ for (auto x : mx[v]){ dist[x.s] = x.f; } for (auto x : mx[to]) { dist[x.s] = max(dist[x.s], x.f + 1); } for (auto& x : mx[v]){ x.f = max(x.f, dist[x.s]); dist[x.s] = 0; } for (auto x : mx[to]){ if (dist[x.s] == 0) continue; mx[v].pb({x.f+1, x.s}); dist[x.s] = 0; } } sort(mx[v].rbegin(), mx[v].rend()); while (mx[v].size() > b) mx[v].pop_back(); if (mx[v].size() < b) mx[v].pb({0, v}); } void calc(int v){ if (busy[v]) dp[v] = -1; for (auto to : ed[v]){ if (dp[to] == -1) continue; dp[v] = max(dp[v], dp[to] + 1); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m, q; cin >> n >> m >> q; ed.resize(n+1); mx.resize(n+1); dist.resize(n+1); busy.resize(n+1); dp.resize(n+1); for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; ed[v].pb(u); } for (int i = 1; i <= n; ++i) { dfs(i); } for (int i = 0; i < q; ++i) { int t, y; cin >> t >> y; vector<int> cur(y); for (int j = 0; j < y; ++j) { cin >> cur[j]; busy[cur[j]] = true; } if (y < b){ int ans = -1; for (auto x : mx[t]){ //cout << x.f << " " << x.s << "\n"; if (!busy[x.s]) { ans = x.f; break; } } cout << ans << "\n"; } else{ dp.assign(n+1, 0); for (int j = 1; j <= t; ++j) { calc(j); } cout << dp[t] << "\n"; } for (auto x : cur) busy[x] = false; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...