제출 #1168806

#제출 시각아이디문제언어결과실행 시간메모리
1168806chikien2009Bitaro’s Party (JOI18_bitaro)C++20
7 / 100
2094 ms9620 KiB
#include <bits/stdc++.h> using namespace std; inline void setup() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int n, m, q, a, b, s[100000]; const int block_size = 320; vector<int> g[100000]; vector<pair<int, int>> f[100000], v; bool banned[100000]; int main() { setup(); cin >> n >> m >> q; while (m--) { cin >> a >> b; g[b - 1].push_back(a - 1); } fill_n(s, n, -1); for (int i = 0; i < n; ++i) { v = {{0, i}}; for (auto &j : g[i]) { for (auto &k : f[j]) { v.push_back({k.first + 1, k.second}); } } sort(v.begin(), v.end(), greater<pair<int, int>>()); for (int j = 0; j < v.size() && f[i].size() < block_size; ++j) { if (s[v[j].second] != i) { f[i].push_back(v[j]); s[v[j].second] = i; } } } while (q--) { cin >> a >> b; v.clear(); v.resize(b); a--; for (int i = 0; i < v.size(); ++i) { cin >> v[i].first; v[i].first --; banned[v[i].first] = true; } if (b < block_size) { b = -1; for (auto & i : f[a]) { if (!banned[i.second]) { b = i.first; break; } } } else { b = -1; fill_n(s, n, -1); s[a] = 0; for (int i = a; i >= 0; --i) { if (s[i] != -1) { if (!banned[i]) { b = max(b, s[i]); } for (auto & j : g[i]) { s[j] = max(s[j], s[i] + 1); } } } } for (int i = 0; i < v.size(); ++i) { banned[v[i].first] = false; } cout << b << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...