Submission #1150453

#TimeUsernameProblemLanguageResultExecution timeMemory
1150453t6stksBitaro’s Party (JOI18_bitaro)C++20
14 / 100
829 ms240236 KiB
#include <bits/stdc++.h> #define SZ(x) ((int)(x).size()) #define ALL(x) x.begin(), x.end() #define F first #define S second #define PB push_back using namespace std; using ll = long long; using vi = vector<int>; using vl = vector<ll>; using vvi = vector<vi>; using vvl = vector<vl>; using pii = pair<int, int>; using pll = pair<ll, ll>; using vii = vector<pii>; using vll = vector<pll>; const int B = 100; const int maxn = 2e5 + 5; vector<int> from[maxn]; bitset<maxn> blocked; void sol() { int n, m, q; cin >> n >> m >> q; while (m--) { int u, v; cin >> u >> v; from[--v].PB(--u); } vector<vii> best(n); for (int u = 0; u < n; u++) { best[u].PB({0, u}); for (int v: from[u]) { for (const pii& p: best[v]) { best[u].PB({p.F + 1, p.S}); } } sort(ALL(best[u]), greater<>()); while (SZ(best[u]) > B) best[u].pop_back(); } while (q--) { int t, y; cin >> t >> y; --t; vector<int> yy(y); for (int& x: yy) { cin >> x; --x; } if (y >= B) { vector<int> dp(t + 1); for (int x: yy) { if (x <= t) dp[x] = -1; } for (int i = 0; i <= t; i++) { for (int v: from[i]) { if (dp[v] == -1) continue; dp[i] = max(dp[i], dp[v] + 1); } } cout << dp[t] << '\n'; } else { for (int x: yy) blocked[x] = 1; bool ok = 0; for (auto &[dis, v]: best[t]) { if (!blocked[v]) { cout << dis << '\n'; ok = 1; break; } } if (!ok) cout << -1 << '\n'; for (int x: yy) blocked[x] = 0; } } } signed main() { cin.tie(0)->sync_with_stdio(0); sol(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...