Submission #1215171

#TimeUsernameProblemLanguageResultExecution timeMemory
1215171mychecksedadBitaro’s Party (JOI18_bitaro)C++20
0 / 100
46 ms74312 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30; int n, m, q; vi g[N], G[N]; vector<pii> T[N]; void solve(){ cin >> n >> m >> q; for(int i = 1; i <= m; ++i){ int u, v; cin >> u >> v; g[v].pb(u); G[u].pb(v); } for(int i = 1; i <= n; ++i){ T[i].pb({0, i}); } vector<bool> VIS(n+1); vi used; for(int i = 1; i <= n; ++i){ for(int u: g[i]){ vector<pii> P; int ptr = 0; for(int j = 0; j < T[i].size(); ++j){ while(ptr < T[u].size() && T[u][ptr].ff + 1 >= T[i][j].ff){ P.pb({T[u][ptr].ff + 1, T[u][ptr].ss}); ++ptr; } P.pb(T[i][j]); } while(ptr < T[u].size()) {P.pb({T[u][ptr].ff + 1, T[u][ptr].ss}); ptr++;} T[i].clear(); for(int j = 0; j < P.size() && T[i].size() <= 400; ++j){ if(VIS[P[j].ss]) continue; T[i].pb(P[j]); used.pb(P[j].ss); VIS[P[j].ss] = 1; } for(int x: used) VIS[x] = 0; used.clear(); } } vector<vi> Q(q + 1); vector<bool> bad(n + 1); for(int i = 1; i <= q; ++i){ int y, v; cin >> v >> y; Q[i].resize(y); for(int &x: Q[i]){ cin >> x; bad[x] = 1; } if(y >= 400){ vi dp(n + 1, 0); for(int x: Q[i]) dp[x] = -MOD; for(int j = 1; j <= n; ++j){ for(int u: G[j]) dp[u] = max(dp[u], dp[j] + 1); } cout << dp[v] << '\n'; }else{ int ans = -1; for(auto [dist, x]: T[v]){ if(!bad[x]){ ans = dist; break; } } cout << ans << '\n'; } for(int &x: Q[i]){ bad[x] = 0; } } } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); en; } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...