제출 #624388

#제출 시각아이디문제언어결과실행 시간메모리
624388radalBitaro’s Party (JOI18_bitaro)C++17
100 / 100
1553 ms405728 KiB
#include <bits/stdc++.h> #pragma GCC target("sse,sse2,avx2") #pragma GCC optimize("unroll-loops,O2") #define rep(i,l,r) for (int i = l; i < r; i++) #define repr(i,r,l) for (int i = r; i >= l; i--) #define X first #define Y second #define all(x) (x).begin() , (x).end() #define pb push_back #define endl '\n' #define debug(x) cerr << #x << " : " << x << endl; using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pll; constexpr int N = 1e5+10,mod = 998244353,inf = 1e9+10,sq = 500; inline int mkay(int a,int b){ if (a+b >= mod) return a+b-mod; if (a+b < 0) return a+b+mod; return a+b; } inline int poww(int a,int k){ if (k < 0) return 0; int z = 1; while (k){ if (k&1) z = 1ll*z*a%mod; a = 1ll*a*a%mod; k /= 2; } return z; } vector<int> out[N],in[N]; int d[N]; bool bad[N]; pll mx[N][sq]; bool vis[N]; inline void mg(int u,int v){ int po = 0,po2 = 0; vector<pll> tmp; int sz = 0; while(sz < sq && (po < sq || po2 < sq)){ if (po == sq || mx[u][po].Y == -1){ int x = mx[v][po2].Y; if (x == -1){ break; } if (vis[x]){ po2++; continue; } sz++; vis[x] = 1; tmp.pb({mx[v][po2].X+1,x}); continue; } if (po2 == sq || mx[v][po2].Y == -1){ int x = mx[u][po].Y; if (x == -1){ break; } if (vis[x]){ po++; continue; } sz++; vis[x] = 1; tmp.pb(mx[u][po]); continue; } int x = mx[u][po].Y; if (vis[x]){ po++; continue; } int y = mx[v][po2].Y; if (vis[y]){ po2++; continue; } sz++; if (mx[u][po].X >= mx[v][po2].X+1){ vis[x] = 1; tmp.pb(mx[u][po]); po++; } else{ vis[y] = 1; tmp.pb({mx[v][po2].X+1,y}); po2++; } } rep(i,0,sz) mx[u][i] = tmp[i]; rep(i,sz,sq) mx[u][i] = {-inf,-1}; rep(i,0,sq){ int x = mx[v][i].Y,y = mx[u][i].Y; if (x >= 0) vis[x] = 0; if (y >= 0) vis[y] = 0; } } int main(){ ios :: sync_with_stdio(0); cin.tie(0); int n,m,q; cin >> n >> m >> q; rep(i,0,m){ int u,v; cin >> u >> v; out[u].pb(v); in[v].pb(u); } rep(i,1,n+1){ mx[i][0] = {0,i}; rep(j,1,sq) mx[i][j] = {-inf,-1}; } rep (i,2,n+1){ for (int j : in[i]){ mg(i,j); } } while (q--){ int u,t; vector<int> ve; cin >> u >> t; ve.resize(t); rep(i,0,t){ cin >> ve[i]; bad[ve[i]] = 1; } if (t < sq){ rep(i,0,sq){ if (mx[u][i].Y == -1){ cout << -1 << endl; break; } if (!bad[mx[u][i].Y]){ cout << mx[u][i].X << endl; break; } } for (int x : ve) bad[x] = 0; continue; } int mx = -1; memset(d,128,sizeof d); d[u] = 0; repr(i,u,1){ if (!bad[i]) mx = max(mx,d[i]); for (int j : in[i]){ d[j] = max(d[j],d[i]+1); } } for (int x : ve) bad[x] = 0; cout << mx << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...