제출 #941712

#제출 시각아이디문제언어결과실행 시간메모리
941712oblantisBitaro’s Party (JOI18_bitaro)C++17
100 / 100
1554 ms261500 KiB
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #pragma GCC optimize("O3,unroll-loops") #include <bits/stdc++.h> #define all(v) v.begin(), v.end() #define pb push_back #define ss second #define ff first #define vt vector using namespace std; typedef long long ll; typedef pair<int, int> pii; const int inf = 1e9; const int mod = 1e9+7; const int maxn = 1e5 + 1; vt<int> g[maxn]; vt<pii> hv[maxn]; bool was[maxn]; int dp[maxn]; void solve() { int n, m, q, sq; cin >> n >> m >> q; sq = sqrt(n); if(sq * sq != n)sq++; for(int i = 0, u, v; i < m; i++){ cin >> u >> v; g[--v].pb(--u); } for(int i = 0; i < n; i++){ hv[i].pb({0, i}); for(auto k : g[i]){ vt<pii> res; int j = hv[i].size() - 1, o = hv[k].size() - 1, sz = 0; while((j >= 0 || o >= 0) && sz < sq){ while(j >= 0 && was[hv[i][j].ss])j--; while(o >= 0 && was[hv[k][o].ss])o--; if(j < 0 && o < 0)break; if(o < 0)res.pb(hv[i][j--]); else if(j < 0)res.pb({hv[k][o].ff + 1, hv[k][o].ss}); else if(hv[i][j].ff > hv[k][o].ff + 1)res.pb(hv[i][j--]); else res.pb({hv[k][o].ff + 1, hv[k][o].ss}); was[res.back().ss] = 1; sz++; } for(auto j : res)was[j.ss] = 0; reverse(all(res)); hv[i] = res; } } for(int i = 0; i < q; i++){ int k, t; cin >> t >> k; --t; vt<int> x(k); for(int j = 0; j < k; j++){ cin >> x[j]; was[--x[j]] = 1; } if(k >= sq){ for(int j = 0; j <= t; j++){ if(was[j])dp[j] = -inf; else dp[j] = 0; for(auto o : g[j]){ dp[j] = max(dp[j], dp[o] + 1); } } if(dp[t] < 0)cout << "-1\n"; else cout << dp[t] << '\n'; } else { int sz = hv[t].size() - 1; while(sz >= 0 && was[hv[t][sz].ss]){ sz--; } if(sz < 0)cout << "-1\n"; else cout << hv[t][sz].ff << '\n'; } for(auto j : x)was[j] = 0; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int times = 1; //cin >> times; for(int i = 1; i <= times; i++) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...