제출 #693265

#제출 시각아이디문제언어결과실행 시간메모리
693265four_specksBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2085 ms43640 KiB
#include <bits/stdc++.h> using namespace std; namespace { } // namespace void solve() { const int SQ = 150; int n, m, q; cin >> n >> m >> q; vector<vector<int>> adj(n); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v, --u, --v; adj[v].push_back(u); } vector<vector<pair<int, int>>> take(n); for (int i = 0; i < n; i++) { vector<pair<int, int>> can; can.emplace_back(i, 0); for (int j : adj[i]) { for (auto [l, k] : take[j]) can.emplace_back(k, l + 1); } sort(can.begin(), can.end(), greater<>()); for (int j = 0; j < (int)can.size(); j++) { if (j == 0 || can[j].second != can[j - 1].second) take[i].emplace_back(can[j].second, can[j].first); } sort(take[i].begin(), take[i].end(), greater<>()); if ((int)take[i].size() > SQ) take[i].erase(take[i].begin() + SQ, take[i].end()); } vector<bool> bad(n); for (int c = 0; c < q; c++) { int u, y; cin >> u >> y, --u; vector<int> busy(y); for (int &v : busy) cin >> v, --v; if (y >= SQ) { vector<int> dp(u + 1); for (int v : busy) { if (v <= u) dp[v] = -1; } for (int i = 0; i <= u; i++) { for (int j : adj[i]) { if (dp[j] != -1) dp[i] = max(dp[i], dp[j] + 1); } } cout << dp[u] << '\n'; } else { for (int v : busy) bad[v] = 1; int res = -1; for (auto [l, v] : take[u]) { if (!bad[v]) { res = l; break; } } cout << res << '\n'; for (int v : busy) bad[v] = 0; } } } int main() { ios_base::sync_with_stdio(false), cin.tie(NULL); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...