제출 #1150447

#제출 시각아이디문제언어결과실행 시간메모리
1150447t6stksBitaro’s Party (JOI18_bitaro)C++20
0 / 100
8 ms7240 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 = 150; const int maxn = 1e5 + 5; vector<int> from[maxn]; vii best[maxn]; int n, m, q; void init() { for (int u = 0; u < n; u++) { best[u].PB({0, u}); for (int v: from[u]) { for (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(); } } bitset<maxn> blocked; void sol() { cin >> n >> m >> q; while (m--) { int u, v; cin >> u >> v; from[--v].PB(--u); } init(); 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) 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...