Submission #1168820

#TimeUsernameProblemLanguageResultExecution timeMemory
1168820chikien2009Bitaro’s Party (JOI18_bitaro)C++20
7 / 100
2069 ms9044 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, c, s[100000], d[100000]; const int block_size = 200; vector<int> g[100000]; vector<pair<int, int>> f[100000]; 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) { vector<pair<int, int>> 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; a--; c = -1; for (int i = 0; i < b; ++i) { cin >> d[i]; d[i] --; banned[d[i]] = true; } if (b < block_size) { for (auto & i : f[a]) { if (!banned[i.second]) { c = i.first; break; } } } else { fill_n(s, n, -1); s[a] = 0; for (int i = a; i >= 0; --i) { if (s[i] != -1) { if (!banned[i]) { c = max(c, s[i]); } for (auto & j : g[i]) { s[j] = max(s[j], s[i] + 1); } } } } for (int i = 0; i < b; ++i) { banned[d[i]] = false; } cout << c << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...