Submission #1043657

#TimeUsernameProblemLanguageResultExecution timeMemory
1043657khanhtbBitaro’s Party (JOI18_bitaro)C++14
0 / 100
1 ms6492 KiB
// #pragma GCC optimize("O3,unroll-loops") #include <bits/stdc++.h> #define ll long long #define ull unsigned long long #define ld long double #define pb push_back #define pf push_front #define vi vector<ll> #define vii vector<vi> #define pll pair<ll, ll> #define vpll vector<pll> #define all(a) a.begin(), a.end() #define fi first #define se second using namespace std; const ll mod = 998244353; const ll inf = 2e18; const ll B = 320; const ll N = 1e5+8; int n,m,q; vector<int> g[N]; vector<pair<int,int>> best[N]; int d[N],vst[N],bad[N],dp[N]; void solve(){ cin >> n >> m >> q; for(int i = 1; i <= m; i++){ int u,v;cin >> u >> v; g[v].pb(u); } for(int u = 1; u <= n; u++){ vector<int> cur; for(int v:g[u]){ for(pair<int,int> ed:best[v]){ int vv = ed.se, w = ed.fi; if(vst[vv] == u) d[vv] = max(d[vv],w+1); else{ vst[vv] = u; d[vv] = w+1; cur.pb(vv); } } } for(int v:cur) best[u].pb({d[v],v}); best[u].pb({0,u}); sort(all(best[u]),greater<pair<int,int>>()); while(best[u].size() > B) best[u].pop_back(); } while(q--){ int t,s;cin >> t >> s; for(int i = 1; i <= s; i++){ int x;cin >> x; bad[x] = q; } int ans = -1; if(s < B){ for(pair<int,int> v:best[t]){ if(bad[v.se] != q){ ans = v.fi; break; } } } else{ fill(dp,dp+n+1,-1); for(int u = 1; u <= t; u++){ if(bad[u] != q) dp[u] = 0; for(int v:g[u]){ if(dp[v] != -1) dp[u] = max(dp[u],dp[v]+1); } } ans = dp[t]; } cout << ans << '\n'; } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // if (fopen("test.inp", "r")) { // freopen("test.inp", "r", stdin); // freopen("test.out", "w", stdout); // } ll T = 1; // cin >> T; for (ll i = 1; i <= T; i++) { solve(); cout << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...