제출 #389192

#제출 시각아이디문제언어결과실행 시간메모리
389192sinamhdvBitaro’s Party (JOI18_bitaro)C++11
14 / 100
2078 ms51660 KiB
// JOI18_bitaro #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int mod = 1000 * 1000 * 1000 + 7; const int INF = 1e9 + 100; const ll LINF = 1e18 + 100; #ifdef DEBUG #define dbg(x) cout << #x << " = " << (x) << endl << flush; #define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; } #else #define dbg(x) ; #define dbgr(s, f) ; #endif #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define all(x) (x).begin(), (x).end() #define pb push_back #define mp make_pair #define fr first #define sc second #define endl '\n' #define MAXN 100100 #define SQ 50 int n, m, q; vector<int> adj[MAXN], badj[MAXN]; pii dp[MAXN][SQ]; int fw[MAXN]; bool busy[MAXN]; bool added[MAXN]; int32_t main(void) { fast_io; cin >> n >> m >> q; FOR(i, 0, m) { int x, y; cin >> x >> y; adj[x].pb(y); badj[y].pb(x); } FOR(i, 0, MAXN) FOR(j, 0, SQ) dp[i][j].fr = -INF; FOR(v, 1, n + 1) { vector<pii> vec; vector<int> advec; for (int u : badj[v]) FOR(i, 0, SQ) vec.pb({dp[u][i].fr + 1, dp[u][i].sc}); vec.pb({0, v}); sort(all(vec), greater<pii>()); int ptr = 0; for (pii p : vec) { if (added[p.sc]) continue; dp[v][ptr++] = p; added[p.sc] = true; advec.pb(p.sc); if (ptr >= SQ) break; } for (; ptr < SQ; ptr++) dp[v][ptr] = {-INF, 0}; for (int u : advec) added[u] = false; } while (q--) { int t, y; cin >> t >> y; vector<int> bs; FOR(i, 0, y) { int x; cin >> x; busy[x] = true; bs.pb(x); } if (y >= SQ) { int ans = -INF; fill(fw, fw + n + 10, -INF); fw[t] = 0; for (int i = n; i >= 1; i--) { for (int u : adj[i]) fw[i] = max(fw[i], fw[u] + 1); if (!busy[i]) ans = max(ans, fw[i]); } if (ans < 0) cout << "-1\n"; else cout << ans << endl; } else { FOR(i, 0, SQ) if (!busy[dp[t][i].sc]) { int ans = dp[t][i].fr; if (ans < 0) cout << "-1\n"; else cout << ans << endl; break; } } for (int u : bs) busy[u] = false; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...