제출 #1150482

#제출 시각아이디문제언어결과실행 시간메모리
1150482t6stksBitaro’s Party (JOI18_bitaro)C++20
100 / 100
827 ms216892 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]; vector<int> adj[maxn]; bitset<maxn> blocked; int mx[maxn]; 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); } memset(mx, -1, sizeof(mx)); for (int u = 0; u < n; u++) { best[u].PB({0, u}); vector<int> used; for (int v: from[u]) { for (const pii& p: best[v]) { if (mx[p.S] == -1) { mx[p.S] = p.F + 1; used.push_back(p.S); } else { mx[p.S] = max(mx[p.S], p.F + 1); } } } for (int x: used) { best[u].PB({mx[x], x}); mx[x] = -1; } 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; blocked[--x] = 1; } if (y >= B) { int ans = -1; vector<int> dp(n + 1, -1e9); dp[t] = 0; for (int i = t; ~i; i--) { for (int v: adj[i]) { dp[i] = max(dp[i], dp[v] + 1); } if (!blocked[i]) ans = max(ans, dp[i]); } cout << ans << '\n'; } 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...