제출 #542437

#제출 시각아이디문제언어결과실행 시간메모리
542437fcwBitaro’s Party (JOI18_bitaro)C++17
14 / 100
774 ms130828 KiB
#include <bits/stdc++.h> #define st first #define nd second using lint = int64_t; constexpr int mod = int(1e9) + 7; constexpr int inf = 0x3f3f3f3f; constexpr int ninf = 0xcfcfcfcf; constexpr lint linf = 0x3f3f3f3f3f3f3f3f; const long double pi = acosl(-1.0); // Returns -1 if a < b, 0 if a = b and 1 if a > b. int cmp_double(double a, double b = 0, double eps = 1e-9) { return a + eps > b ? b + eps > a ? 0 : 1 : -1; } using namespace std; int main() { cin.tie(nullptr)->sync_with_stdio(false); const int SZ = 150; int n, m, q; cin>>n>>m>>q; vector<vector<int>>g(n); vector<int>d(n); for(int i=0;i<m;i++){ int a, b; cin>>a>>b; a--, b--; g[a].push_back(b); d[b]++; } vector<vector<pair<int, int>>>prep(n); for(int i=0;i<n;i++) prep[i] = {{0, i}}; // k-th greatest path to vertice v up to k <= sz + 1 { queue<int>qu; for(int i=0;i<n;i++) if(!d[i]) qu.push(i); while(!qu.empty()){ int u = qu.front(); qu.pop(); for(int v : g[u]){ d[v]--; if(!d[v]) qu.push(v); int pu = (int)prep[u].size(), pv = (int)prep[v].size(); int s = min(pu + pv, SZ); vector<pair<int, int>>c(s); for(int l=0,r=0,i=0;i<s;i++){ if(l < pu && r < pv){ if(prep[u][l].st + 1 >= prep[v][r].st){ c[i] = {prep[u][l].st + 1, prep[u][l].nd}; l++; } else{ c[i] = {prep[v][r].st, prep[v][r].nd}; r++; } } else if(l < pu){ c[i] = {prep[u][l].st + 1, prep[u][l].nd}; l++; } else{ c[i] = {prep[v][r].st, prep[v][r].nd}; r++; } } swap(prep[v], c); } } } vector<bool>w(n); for(int T=0;T<q;T++){ int u, k; cin>>u>>k; u--; vector<int>skip(k); for(int i=0;i<k;i++) cin>>skip[i], skip[i]--; for(int v : skip) w[v] = 1; if(k >= SZ){ for(int i=0;i<=u;i++) d[i] = 0; for(int i=0;i<=u;i++){ for(int v : g[i]){ if(v > u) continue; d[v]++; } } queue<int>qu; vector<int>dp(u+1, -1); for(int i=0;i<=u;i++){ if(!w[i]) dp[i] = 0; if(!d[i]) qu.push(i); } while(!qu.empty()){ int cur = qu.front(); qu.pop(); for(int v : g[cur]){ if(v > u) continue; if(dp[cur] >= 0) dp[v] = max(dp[v], dp[cur] + 1); d[v]--; if(!d[v]) qu.push(v); } } cout<<dp[u]<<"\n"; } else{ int ans = -1; for(auto [dist, v] : prep[u]){ if(w[v]) continue; ans = dist; break; } cout<<ans<<"\n"; } for(int v : skip) w[v] = 0; } return 0; } /* [ ]Leu o problema certo??? [ ]Ver se precisa de long long [ ]Viu o limite dos fors (é n? é m?) [ ]Tamanho do vetor, será que é 2e5 em vez de 1e5?? [ ]Testar sample [ ]Testar casos de borda [ ]1LL no 1LL << i [ ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?) */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...