제출 #1087409

#제출 시각아이디문제언어결과실행 시간메모리
1087409GrayBitaro’s Party (JOI18_bitaro)C++17
14 / 100
1349 ms476500 KiB
// #pragma GCC optimize("Ofast") // #pragma GCC target("sse3,avx2") #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 = INT_MAX; const ll MOD = (ll)1e9+7; const ll B = 100; 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; } } vector<ll> idp; ll brute(ll u, set<ll> &block){ idp.assign(n+1, -1); bdfs(u, idp, block); return idp[u]==-INF?-1:idp[u]; } vector<vector<pair<ll, ll>>> dp; set<pair<ll, pair<ll, ll>>, greater<pair<ll, pair<ll, ll>>>> point; void dfs(ll u, vector<bool> &vis){ vis[u]=1; point.clear(); for (auto v:A[u]){ if (!vis[v]) dfs(v, vis); for (auto ch:dp[v]) dp[u].push_back({ch.ff+1, ch.ss}); } dp[u].push_back({0, u}); sort(dp[u].rbegin(), dp[u].rend()); dp[u].erase(unique(dp[u].begin(), dp[u].end()), dp[u].end()); while (dp[u].size()>B) dp[u].pop_back(); } 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); } // for (ll i=1; i<=n; i++){ // cout << i << ": "; // for (auto v:dp[i]) cout << v.ff << "-" << v.ss << " "; // cout << ln; // } set<ll> blocked; while (q--){ ll t, y; cin >> t >> y; blocked.clear(); 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...