Submission #790516

#TimeUsernameProblemLanguageResultExecution timeMemory
790516KiaRezBitaro’s Party (JOI18_bitaro)C++17
14 / 100
1195 ms223932 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=130, 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, qu, deg[N], mark[N], mark2[N], dist[N]; vector<pii> vec[N]; vector<int> adj[N], rev[N]; void init() { for(int i=1; i<=n; i++) { int v = i; priority_queue<pii, vector<pii>, greater<pii>> pq; for(auto u : rev[v]) { for(int i=size(vec[u])-1; i>=0; i--) { if(mark2[vec[u][i].S] == 1) continue; pq.push({vec[u][i].F+1, vec[u][i].S}); mark2[vec[u][i].S] = 1; if(size(pq) > SQ) { mark2[pq.top().S] = 0; pq.pop(); } } } if(size(pq) < SQ) pq.push({0, v}); while(size(pq)) { vec[v].pb(pq.top()); mark2[pq.top().S] = 0; pq.pop(); } } } void KIAREZ(int v) { fill(dist, dist+n+2, -1); for(int i=1; i<=n; i++) { if(mark[i] == 0) dist[i] = 0; int u = i; for(auto w : rev[u]) { if(dist[w]>0 || mark[w]==0) dist[u] = max(dist[u], dist[w]+1); } } 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>>qu; for(int v,u,i=1; i<=m; i++) { cin>>v>>u; adj[v].pb(u); rev[u].pb(v); } init(); while(qu--) { 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...