제출 #719614

#제출 시각아이디문제언어결과실행 시간메모리
719614S2speedBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2048 ms11872 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize ("Ofast") #define all(x) x.begin() , x.end() #define sze(x) (ll)(x.size()) #define mp(x , y) make_pair(x , y) #define wall cout<<"--------------------------------------\n"; typedef long long int ll; typedef pair<ll , ll> pll; typedef pair<int , int> pii; typedef double db; typedef pair<pll , ll> plll; typedef pair<int , pii> piii; typedef pair<pll , pll> pllll; const ll maxn = 1e5 + 18 , md = 1e9 + 7 , inf = 2e8; int n , m , q , sq; vector<int> adj[maxn] , qu; vector<pii> f[maxn]; bool mark[maxn]; int dp[maxn]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m>>q; sq = min(n , 300); for(int i = 0 ; i < m ; i++){ int v , u; cin>>v>>u; v--; u--; adj[u].push_back(v); } for(int i = 0 ; i < n ; i++){ vector<pii> tmp; tmp.push_back({-1 , i}); for(auto j : adj[i]){ for(auto k : f[j]){ tmp.push_back(k); } } sort(all(tmp) , greater<pii>()); for(auto p : tmp){ if(sze(f[i]) == sq) break; if(mark[p.second]) continue; mark[p.second] = true; f[i].push_back({p.first + 1 , p.second}); } for(auto p : f[i]){ mark[p.second] = false; } } for(int e = 0 ; e < q ; e++){ qu.clear(); int v , k , res = -1; cin>>v>>k; v--; for(int i = 0 ; i < k ; i++){ int u; cin>>u; u--; qu.push_back(u); mark[u] = true; } if(k < sq){ for(auto p : f[v]){ if(mark[p.second]) continue; res = p.first; break; } } else { for(int i = 0 ; i <= v ; i++){ int h = (mark[i] ? -inf : 0); for(auto j : adj[i]){ h = max(dp[j] + 1 , h); } dp[i] = h; } res = (dp[v] < 0 ? -1 : dp[v]); } cout<<res<<'\n'; for(auto u : qu){ mark[u] = false; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...