제출 #128890

#제출 시각아이디문제언어결과실행 시간메모리
128890RockyBBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2045 ms5492 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 = 150; 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; } } int sz[MAX_N], used[MAX_N]; pair <int, int> bfr[MAX_N]; pair <int, int> dist[MAX_N][K]; void pre() { rep(i, 1, n) { int S = 0; bfr[S++] = {0, i}; for (auto to : g[i]) { for (int j = 0; j < sz[to]; j++) { auto it = dist[to][j]; bfr[S++] = {it.f + 1, it.s}; } } /* cerr << S << nl; continue; for (int j = 0; j < S; j++) cerr << bfr[j].f << ' ' << bfr[j].s << nl; */ sort(bfr, bfr + S, greater < pair <int, int> > () ); /* cerr << "check->"; for (int j = 0; j < S; j++) cerr << bfr[j].f << ' ' << bfr[j].s << nl; continue */; rep(j, 0, S - 1) { if (used[bfr[j].s] == i) continue; if (sz[i] < K) { used[bfr[j].s] = i; dist[i][sz[i]++] = bfr[j]; } else break; } } /* rep(i, 1, n) { cerr << i << " -> "; rep(j, 0, sz[i] - 1) cerr << dist[i][j].s << ' '; cerr << nl; } */ } void fast() { int res = -1; rep(i, 1, k) { ban[a[i]] = 1; } rep(i, 0, sz[T] - 1) { if (!ban[dist[T][i].s]) { res = max(res, dist[T][i].f); break; } } 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); } //rep(i, 1, n) for (auto to : g[i]) if (!to) assert(0); pre(); //for (auto it : st[2]) cerr << it.f << ' ' << it.s << nl; rep(i, 1, q) { read(); //fast(); 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...