제출 #1094146

#제출 시각아이디문제언어결과실행 시간메모리
1094146BLOBVISGODBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2031 ms6420 KiB
#include "bits/stdc++.h" using namespace std; #define rep(i,a,b) for(int i=(a); i<(b); ++i) #define all(x) x.begin(),x.end() #define sz(x) int(x.size()) typedef long long ll; typedef unsigned long long ull; typedef vector<int> vi; typedef vector<vi> vvi; const int oo = 1e9; const int B = 211; const int N = 2e5+10; bool seen[N]; int dp[N]; int main(){ cin.tie(NULL),cin.sync_with_stdio(false); int n,m,q; cin >> n >> m >> q; vvi rev(n); rep(i,0,m){ int s,e; cin >> s >> e; s--,e--; rev[e].push_back(s); } vector<vector<array<int,2>>> prec(n); for(auto& v : prec) v.reserve(B+2); rep(i,0,n){ vector<array<int,2>> cur = {{-1,i}}; for (auto to : rev[i]) cur.insert(end(cur),all(prec[to])); sort(all(cur)); reverse(all(cur)); for(int j = 0; j < sz(cur) and sz(prec[i]) < B+2; ++j) { auto [v,at] = cur[j]; if (!seen[at]){ seen[at] = 1; prec[i].push_back({v+1,at}); } } for(auto [v,at] : prec[i]) seen[at] = 0; } while(q--){ int t,y; cin >> t >> y; t--; vector<int> c(y); rep(i,0,y) cin >> c[i], c[i]--; if (y>B){ fill(dp,dp+t+1,0); for(auto at : c) dp[at] = -oo; for(int i = 0; i <= t; ++i){ for(auto to : rev[i]) dp[i] = max(dp[i],dp[to]+1); } if (dp[t]<0) cout << "-1\n"; else cout << dp[t] << '\n'; }else{ bool done = 0; for(auto [v, at] : prec[t]) if (!binary_search(all(c),at)){ cout << v << '\n'; done = 1; break; }if (!done){ cout << "-1\n"; } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...