Submission #963274

#TimeUsernameProblemLanguageResultExecution timeMemory
963274TimAniBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2071 ms205656 KiB
//start-time: 2024-04-14 19:39:32 #include <bits/stdc++.h> using namespace std; using ll = long long; const int w = 330; void solve(){ int n, m, q; cin >> n >> m >> q; vector<vector<int>> g(n); vector<vector<int>> gR(n); for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; u--; v--; g[u].push_back(v); gR[v].push_back(u); } vector<int> topo(n); iota(topo.begin(), topo.end(), 0); vector<vector<array<int, 2>>> dp(n); for(auto u : topo){ vector<int> val(n, -1), aux; aux.push_back(u); val[u] = 0; for(auto v : gR[u]){ for(auto [value, ind] : dp[v]){ aux.push_back(ind); val[ind] = max(val[ind], value + 1); } } sort(aux.begin(), aux.end()); aux.erase(unique(aux.begin(), aux.end()), aux.end()); sort(aux.begin(), aux.end(), [&](int a, int b){ return val[a] > val[b]; }); for(auto el : aux){ if(dp[u].size() < w){ dp[u].push_back({val[el], el}); } } } for(int i = 0; i < q; i++){ int u, y; cin >> u >> y; u--; vector<bool> c(100'001); for(int j = 0; j < y; j++){ ll a; cin >> a; c[--a] = 1; } int ans = -1; if(y < w) { for(auto [v, i] : dp[u]){ if(!c[i]){ ans = max(ans, v); } } } else { vector<int> naive(n); for(auto v : topo){ naive[v] = c[v] ? -1 : 0; for(auto el : gR[v]){ naive[v] = max(naive[v], naive[el] + (naive[el] != -1)); } } ans = naive[u]; } cout << ans << endl; } } int main() { cin.tie(0)->sync_with_stdio(0); ll T = 1; //cin >> T; while(T--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...