제출 #128857

#제출 시각아이디문제언어결과실행 시간메모리
128857RockyBBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2054 ms159224 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 = 1000; 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 > > dist[MAX_N]; int used[MAX_N]; void pre() { rep(i, 1, n) { dist[i].pb({0, i}); for (auto to : g[i]) { for (auto it : dist[to]) { dist[i].pb({it.f + 1, it.s}); } } sort(all(dist[i]), greater < pair <int, int> > () ); vector < pair <int, int > > nw; for (auto it : dist[i]) { if (sz(nw) < K && used[it.s] != i) { used[it.s] = i; nw.pb(it); } } dist[i] = nw; } } void fast() { int res = -1; rep(i, 1, k) { ban[a[i]] = 1; } for (auto it : dist[T]) { if (!ban[it.s]) { res = max(res, it.f); } } rep(i, 1, k) { ban[a[i]] = 0; } cout << res << nl; //cerr << "DA\n"; } int main() { ios_base :: sync_with_stdio(0); cin.tie(0), cout.tie(0); #ifdef IOI freopen ("in.txt", "r", stdin); freopen ("B.out", "w", stdout); #endif cin >> n >> m >> q; rep(i, 1, m) { int s, e; cin >> s >> e; g[e].pb(s); } pre(); //for (auto it : st[2]) cerr << it.f << ' ' << it.s << nl; 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...