제출 #1087134

#제출 시각아이디문제언어결과실행 시간메모리
1087134GrayBitaro’s Party (JOI18_bitaro)C++17
14 / 100
2053 ms23892 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define ff first #define ss second #define ln "\n" using namespace std; const ll INF = 2e18; const ll MOD = (ll)1e9+7; const ll B = 0; ll n, m, q; vector<vector<ll>> A; void bdfs(ll u, vector<ll> &dp, set<ll> &blocked){ dp[u]=0; for (auto v:A[u]){ if (dp[v]==-1){ bdfs(v, dp, blocked); } dp[u]=max(dp[u], dp[v]+1); } if (dp[u]==0 and blocked.count(u)){ dp[u]=-INF; } } ll brute(ll u, set<ll> &block){ vector<ll> dp(n+1, -1); bdfs(u, dp, block); return dp[u]==-INF?-1:dp[u]; } vector<vector<pair<ll, ll>>> dp; void append(pair<ll, ll> x, vector<pair<ll, ll>> &st){ st.push_back(x); } void dfs(ll u, vector<bool> &vis){ vis[u]=1; for (auto v:A[u]){ if (!vis[v]) dfs(v, vis); for (auto ch:dp[v]){ append({ch.ff+1, ch.ss}, dp[u]); } } append({0, u}, dp[u]); sort(dp[u].rbegin(), dp[u].rend()); while (dp[u].size()>B) dp[u].pop_back(); reverse(dp[u].begin(), dp[u].end()); } void solve(){ cin >> n >> m >> q; A.resize(n+1); for (ll i=0; i<m; i++){ ll u, v; cin >> u >> v; A[v].push_back(u); } dp.resize(n+1); vector<bool> vis(n+1); for (ll i=1; i<=n; i++){ if (!vis[i]) dfs(i, vis); } while (q--){ ll t, y; cin >> t >> y; set<ll> blocked; for (ll i=0; i<y; i++){ ll x; cin >> x; blocked.insert(x); } if (y<B){ ll mx=-1; for (auto ch:dp[t]){ if (!blocked.count(ch.ss)) mx=max(mx, ch.ff); } cout << mx << ln; }else{ cout << brute(t, blocked) << ln; } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(nullptr); ll t=1; // cin >> t; while (t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...