제출 #624931

#제출 시각아이디문제언어결과실행 시간메모리
624931ArnchBitaro’s Party (JOI18_bitaro)C++17
0 / 100
199 ms524288 KiB
// oooo /* har chi delet mikhad bebar ~ gitar o ba khodet nabar! ~ ;Amoo_Hasan; */ #include<bits/stdc++.h> //#pragma GCC optimize("O3,no-stack-protector,unroll-loops") //#pragma GCC target("avx2,fma") using namespace std; typedef long long ll; typedef long double ld; #define Sz(x) int((x).size()) #define All(x) (x).begin(), (x).end() #define wtf(x) cout<<#x <<" : " <<x <<endl #define endl '\n' constexpr ll inf = 1e18, N = 1e5 + 10, SQ = 1010; int n, m, q, ans_t[N]; int t[N], y[N]; pair<int, int> dp[N][SQ]; bool mark[N], ex[N]; vector<int> adj[N], radj[N], vc[N], topol; void dfs(int x) { mark[x] = 1; for(auto j : adj[x]) { if(mark[j]) continue; dfs(j); } topol.push_back(x); } int main() { ios :: sync_with_stdio(0), cin.tie(0); cin >>n >>m >>q; for(int i = 0; i < m; i++) { int u, v; cin >>u >>v; adj[u].push_back(v); radj[v].push_back(u); } for(int i = 1; i <= n; i++) { if(!mark[i]) dfs(i); } reverse(All(topol)); for(int i = 0; i < q; i++) { cin >>t[i] >>y[i]; if(y[i] >= SQ) { vector<int> his; for(int j = 0; j < y[i]; j++) { int u; cin >>u; his.push_back(u); ex[u] = 1; } int ans = -1; memset(mark, 0, sizeof(mark)); priority_queue<pair<int, int> > pq; pq.push({0, t[i]}); while(!pq.empty()) { int p = pq.top().second, q = pq.top().first; pq.pop(); mark[p] = 1; if(!ex[p]) ans = max(ans, q); for(auto j : radj[p]) { if(mark[j]) continue; pq.push({q + 1, j}); } } for(auto j : his) { ex[j] = 0; } his.clear(); ans_t[i] = ans; continue; } for(int j = 0; j < y[i]; j++) { int u; cin >>u; vc[i].push_back(u); } } memset(dp, -1, sizeof(dp)); for(auto u : topol) { int ptr = 0; priority_queue<pair<pair<int, int>, pair<int, int> > > pq; for(auto v : radj[u]) { pq.push({dp[v][0], {0, v}}); } memset(mark, 0, sizeof(mark)); while(!pq.empty() && ptr < SQ) { int v = pq.top().second.second, ptrv = pq.top().second.first; pair<int, int> val = pq.top().first; pq.pop(); if(val.first == -1) break; if(!mark[val.second]) dp[u][ptr++] = {val.first + 1, val.second}; mark[val.second] = 1; pq.push({dp[v][++ptrv], {ptrv, v}}); } if(ptr < SQ) dp[u][ptr] = {0, u}; } /*cout<<"------------" <<endl; for(auto j : topol) cout<<j <<' '; cout<<endl; */ // cout<<dp[4][1].first <<" " <<dp[4][1].second <<endl; for(int i = 0; i < q; i++) { if(y[i] >= SQ) cout<<ans_t[i] <<endl; else { bool f = 0; for(auto j : vc[i]) { ex[j] = 1; } for(int j = 0; j < SQ; j++) { if(!ex[dp[t[i]][j].second]) { cout<<dp[t[i]][j].first <<endl; f = 1; break; } } if(!f) { cout<<-1 <<endl; } for(auto j : vc[i]) { ex[j] = 0; } } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...