Submission #1150459

#TimeUsernameProblemLanguageResultExecution timeMemory
1150459t6stksBitaro’s Party (JOI18_bitaro)C++20
0 / 100
8 ms8776 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 = 1e5 + 5; vector<int> from[maxn]; vector<int> adj[maxn]; bitset<maxn> blocked; vii best[maxn]; void sol() { int n, m, q; cin >> n >> m >> q; while (m--) { int u, v; cin >> u >> v; from[--v].PB(--u); adj[u].push_back(v); } 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; blocked[x] = 1; } if (y >= B) { int ans = -1; vector<int> dp(n + 1, -1e9); dp[t] = 0; for (int i = t - 1; ~i; i--) { for (int v: adj[i]) { dp[i] = max(dp[i], dp[v] + 1); } if (!blocked[i]) ans = max(ans, dp[i]); } } else { 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...