제출 #790489

#제출 시각아이디문제언어결과실행 시간메모리
790489KiaRezBitaro’s Party (JOI18_bitaro)C++17
14 / 100
2049 ms124424 KiB
/* IN THE NAME OF GOD */ #include <bits/stdc++.h> // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef pair<int, pii> ipii; typedef pair<pii, int> piii; typedef pair<ll, pll> lpll; typedef pair<pll, ll> plll; typedef pair<pii, pii> piipii; typedef pair<pll, pll> pllpll; typedef long double ld; #define F first #define S second #define Mp make_pair #define pb push_back #define pf push_front #define size(x) ((ll)x.size()) #define all(x) (x).begin(),(x).end() #define kill(x) cout << x << '\n', exit(0); #define set_dec(x) cout << fixed << setprecision(x); #define ios ios_base::sync_with_stdio(false), cin.tie(0) #define fuck(x) cout << "(" << #x << " , " << x << ")" << endl #define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout); const int N = 2e5+25, SQ=70, lg=18; ll Mod = 1e9+7; //ll Mod = 998244353; ll MOD(ll a, ll mod=Mod) {return (a>=0&&a<mod ? a : ((a%mod+mod)%mod));} ll max(ll a, ll b) {return (a>b ? a : b);} ll min(ll a, ll b) {return (a<b ? a : b);} ll abso(ll a) {return (a<0?-a:a);} inline ll poww(ll a, ll b) { ll ans = 1; a=MOD(a); while (b) { if (b & 1) ans = MOD(ans*a); b >>= 1; a = MOD(a*a); } return ans; } int n, m, q, deg[N], mark[N], mark2[N], dist[N]; vector<pii> vec[N]; vector<int> adj[N], rev[N]; void init() { queue<int> q; for(int i=1; i<=n; i++) { deg[i] = size(rev[i]); if(deg[i] == 0) q.push(i); } while(size(q)) { int v = q.front(); q.pop(); priority_queue<pii, vector<pii>, greater<pii>> pq; for(auto u : rev[v]) { for(int i=size(vec[u])-1; i>=0; i--) { if(size(pq)==SQ && pq.top().F>=vec[u][i].F+1) break; pq.push({vec[u][i].F+1, vec[u][i].S}); if(size(pq) > SQ) pq.pop(); } } //fuck(v); if(size(pq) < SQ) pq.push({0, v}); while(size(pq)) { //cout<<pq.top().F<<' '<<pq.top().S<<endl; vec[v].pb(pq.top()); pq.pop(); } for(auto u : adj[v]) { deg[u]--; if(deg[u] == 0) q.push(u); } } } void KIAREZ(int v) { fill(dist, dist+n+2, 0); fill(deg, deg+n+2, 0); queue<int> q; for(int i=1; i<=n; i++) { deg[i] = size(rev[i]); if(deg[i] == 0) q.push(i); } while(size(q)) { int u = q.front(); q.pop(); for(auto w : adj[u]) { if(mark[u]==0 || dist[u]>0) dist[w] = max(dist[u] + 1, dist[w]); deg[w] --; if(deg[w] == 0)q.push(w); } } if(dist[v]==0 && mark[v]==1) cout<<-1<<endl; else cout<<dist[v]<<endl; } void kiarez(int v) { int ans = -1; for(int i=size(vec[v])-1; i>=0; i--) { if(mark[vec[v][i].S] == 0) {ans = vec[v][i].F; break;} } cout<<ans<<endl; } int main () { ios; cin>>n>>m>>q; for(int v,u,i=1; i<=m; i++) { cin>>v>>u; adj[v].pb(u); rev[u].pb(v); } init(); while(q--) { int t,y; cin>>t>>y; vector<int> c; for(int v,i=1; i<=y; i++) { cin>>v; c.pb(v); mark[v] = 1; } if(y > SQ) { KIAREZ(t); } else { kiarez(t); } for(auto it : c) mark[it] = 0; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...