제출 #128807

#제출 시각아이디문제언어결과실행 시간메모리
128807RockyBBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2054 ms8792 KiB
// In The Name Of The God #include <bits/stdc++.h> #define f first #define s second #define pb push_back #define pp pop_back #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() #define rep(a, b, c) for (int (a) = (b); (a) <= (c); (a)++) #define per(a, b, c) for (int (a) = (b); (a) >= (c); (a)--) #define nl '\n' #define ioi exit(0); using namespace std; const int MAX_N = (int)1e5 + 7; const int K = 200; const int inf = (int)1e9 + 7; int n, m, q; vector <int> g[MAX_N]; int T, k; int tmr; int a[MAX_N], was[MAX_N], dp[MAX_N], h[MAX_N]; bool ban[MAX_N]; int calc(int v) { int res = -inf; if (was[v] == tmr) return dp[v]; was[v] = tmr; if (!ban[v]) res = 0; for (auto to : g[v]) { res = max(res, calc(to) + 1); } return dp[v] = res; } void read() { cin >> T >> k; rep(i, 1, k) { cin >> a[i]; } } void naive() { rep(i, 1, k) { ban[a[i]] = 1; } ++tmr; int res = calc(T); if (res < 0) res = -1; cout << res << nl; rep(i, 1, k) { ban[a[i]] = 0; } } vector < pair <int, int > > st[MAX_N]; void pre() { ++tmr; rep(i, 1, n) { h[i] = calc(i); st[i].pb({h[i], i}); for (auto to : g[i]) { for (auto it : st[to]) st[i].pb(it); } sort(all(st[i])); st[i].erase(unique(all(st[i])), st[i].end()); while (sz(st[i]) > K) st[i].pp(); st[i].shrink_to_fit(); } } void fast() { int res = -1; rep(i, 1, k) { ban[a[i]] = 1; } for (auto it : st[T]) { if (!ban[it.s]) { res = max(res, h[T] - it.f); } } rep(i, 1, k) { ban[a[i]] = 0; } cout << res << nl; } int main() { ios_base :: sync_with_stdio(0); cin.tie(0), cout.tie(0); #ifdef IOI freopen ("in.txt", "r", stdin); #endif cin >> n >> m >> q; rep(i, 1, m) { int s, e; cin >> s >> e; g[e].pb(s); } pre(); rep(i, 1, q) { read(); if (k >= K || T <= K) naive(); else fast(); } ioi }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...