Submission #1089540

#TimeUsernameProblemLanguageResultExecution timeMemory
1089540coldbr3wBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2043 ms7916 KiB
#pragma GCC optimize("Ofast,unroll-loops") #include <bits/stdc++.h> using namespace std; #define ll int #define pll pair<int, int> #define pb push_back #define F first #define S second #define all(x) (x).begin(), (x).end() const ll N = 1e5 + 100; const ll inf = 1e9; const ll mod = 1e9 + 7; const ll block = 222; ll n,m,q; vector<ll>adj[N]; vector<pll>best[N]; ll f[N]; ll vis[N]; bool good[N]; struct ccjv{ll val, u, idx;}; struct cmp{ bool operator()(const ccjv &a, const ccjv &b){ return a.val < b.val; } }; void to_thic_cau(){ cin >> n >> m >> q; for(int i = 1; i <= m;i++){ ll u,v; cin >> u >> v; adj[v].pb(u); } priority_queue<pll> pq; for (int i = 1; i<=n; i++){ pq.push({0,i}); for (auto u : adj[i]){ for (auto x : best[u]){ ll v = x.F, d = x.S; pq.push({d+1,v}); } } for (;best[i].size()<block && pq.size();pq.pop()){ ll d = pq.top().F, v = pq.top().S; if (vis[v]!=i){ vis[v]=i; best[i].pb({v,d}); } } for(;pq.size();pq.pop()); } good[0] = 1; while(q--){ ll t, sz; cin >> t >> sz; vector<ll>vec; for(int i = 1; i <= sz;i++){ ll x; cin >> x; vec.pb(x); good[x] = 1; f[x] = -inf; } if(t >= block){ for(int i = 1; i <= t;i++) for(auto j : adj[i]) f[i] = max(f[i], f[j] + 1); cout << (f[t] < 0 ? -1 : f[t]) << '\n'; for(auto x : vec) good[x] = 0, f[x] = 0; } else{ ll res = -1; for(auto x : best[t]){ ll v = x.F, d = x.S; if(!good[v]) res = max(res, d); } for(auto x : vec) good[x] = 0; cout << res << "\n"; } } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); ll tc = 1; //cin >> tc; while(tc--) to_thic_cau(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...