제출 #67042

#제출 시각아이디문제언어결과실행 시간메모리
67042szawinisBitaro’s Party (JOI18_bitaro)C++17
14 / 100
1708 ms128032 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5+1, INF = 1e9+1; int n, m, q, bsz = 50; vector<int> g[N]; vector<pair<int,int> > dp[N]; bool blocked[N]; int f[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> q; for(int i = 0, s, e; i < m; i++) { cin >> s >> e; --s, --e; g[e].push_back(s); } dp[0].emplace_back(0, 0); for(int i = 1; i < n; i++) { dp[i].emplace_back(0, i); for(int j: g[i]) for(auto x: dp[j]) dp[i].emplace_back(x.first + 1, x.second); nth_element(dp[i].begin(), dp[i].begin() + min(bsz + 10, (int) dp[i].size()), dp[i].end(), greater<pair<int,int> >()); dp[i].resize(min(bsz + 10, (int) dp[i].size())); } while(q--) { int targ, Y; cin >> targ >> Y; --targ; vector<int> C(Y); for(int i = 0; i < Y; i++) { cin >> C[i]; --C[i]; blocked[C[i]] = true; } int res = -INF; if(Y < bsz) { for(auto p: dp[targ]) if(!blocked[p.second]) res = max(p.first, res); } else { fill(f, f+targ+1, 0); for(int i: C) f[i] = -INF; for(int i = 0; i <= targ; i++) { for(int j: g[i]) f[i] = max(f[j] + 1, f[i]); if(f[i] < 0) f[i] = -INF; } res = f[targ]; } if(res == -INF) cout << -1; else cout << res; cout << '\n'; for(int i = 0; i < Y; i++) blocked[C[i]] = false; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...