Submission #1183260

#TimeUsernameProblemLanguageResultExecution timeMemory
1183260GGOSHABBitaro’s Party (JOI18_bitaro)C++20
100 / 100
1877 ms417212 KiB
#ifdef ONPC #define _GLIBCXX_DEBUG #endif #include <bits/stdc++.h> #ifndef ONPC #pragma GCC target("avx") #pragma GCC target("popcnt") #define cerr if (false) cerr #endif using namespace std; #define all(v) begin(v), end(v) #define watch(x) cerr << #x << ": " << x << endl; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> Pint; typedef pair<ll, ll> Pll; mt19937_64 gen64(chrono::steady_clock::now().time_since_epoch().count()); inline ll rnd(ll l = LLONG_MIN, ll r = LLONG_MAX) { return uniform_int_distribution<ll>(l, r)(gen64); } template<class T> bool umin(T &a, const T &b) { return (a > b ? a = b, true : false); } template<class T> bool umax(T &a, const T &b) { return (a < b ? a = b, true : false); } const int mod = 998244353; ll mult(ll a, ll b) { return (a * b) % mod; } template<class T> void add(T &a, const T &b) { a = (a + b) % mod; } const int inf = int(1e9) + 10; const ll INF = ll(1e18) + 10; const int maxn = 1e5 + 10, maxc = 10; constexpr int sqn = 300; vector<int> g[maxn], t[maxn]; void solve() { int n, m, q; cin >> n >> m >> q; for (int e = 0; e < m; ++e) { int v, u; cin >> v >> u; v--, u--; g[v].push_back(u); t[u].push_back(v); } vector<vector<Pint>> small(n); for (int i = 0; i < n; ++i) { small[i].push_back({0, i}); } vector<int> mx(n); vector<bool> used(n); for (int v = 0; v < n; ++v) { vector<int> p; for (int u : t[v]) { for (auto [l, s] : small[u]) { umax(mx[s], l + 1); p.push_back(s); } } for (auto u : p) { if (!used[u]) { used[u] = true; small[v].push_back({mx[u], u}); } } sort(all(small[v]), greater<>()); if (small[v].size() > sqn) { small[v].resize(sqn); } for (int u : p) { used[u] = false; mx[u] = 0; } } vector<int> dp(n); auto calc_big = [&](int t) { for (int i = 0; i < n; ++i) { dp[i] = (used[i] ? -inf : 0); } for (int v = 0; v < n; ++v) { for (int u : g[v]) { umax(dp[u], dp[v] + 1); } } return max(dp[t], -1); }; while (q--) { int t, y; cin >> t >> y; t--; vector<int> c(y); for (auto &v : c) { cin >> v; v--; } for (auto v : c) { used[v] = true; } if (y < sqn) { int ans = -1; for (auto [l, v] : small[t]) { if (!used[v]) { umax(ans, l); } } cout << ans << '\n'; } else { cout << calc_big(t) << '\n'; } for (auto v : c) { used[v] = false; } } } int main() { ios::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; while (t--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...