| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1350676 | jump | Bitaro’s Party (JOI18_bitaro) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define int long long
int RANGE=300;
int n,m,q;
//int height[100010];
//std::vector<std::pair<int,int>> dpV[100010];
//std::vector<std::pair<int,int>> dpVn[100010];
int id[100010];
//int dp[100010];
int tempDp[100010];
bool out[100010];
std::vector<std::pair<int,int>> res[100010];
std::vector<int> adj[100010];
std::vector<int> rev[100010];
std::vector<int> order;
bool visit[100010];
std::stack<int> st;
void dfs(int curr){
if(visit[curr])return;
visit[curr]=true;
for(auto to:adj[curr]){
dfs(to);
}
order.push_back(curr);
return;
}
signed main(){
std::ios_base::sync_with_stdio(0);std::cin.tie(0);
std::cin >> n >> m >> q;
RANGE=300;
for(int i=0;i<m;i++){
int s,e;
std::cin >> s >> e;
adj[s].push_back(e);
rev[e].push_back(s);
}
for(int u = 1;u <= n;u++){
for(int v : rev[u]) id[v] = 0;
for(int j = 0;j < RANGE;j++)
{
std::pair<int,int> mx = {u,0};
for(int v : rev[u])
{
while(id[v]<res[v].size() and out[res[v][id[v]].first]) id[v]++;
if(id[v]<res[v].size() and res[v][id[v]].second+1>mx.second) mx = {res[v][id[v]].first,res[v][id[v]].second+1};
}
res[u].push_back(mx);
out[mx.first] = true;
st.push(mx.first);
if(mx.first==u) break;
else id[mx.first]++;
}
while(!st.empty()) out[st.top()] = false,st.pop();
}
while(q--){
int t,y;
std::vector<int> absent;
std::cin >> t >> y;
for(int i=0;i<y;i++){
int x;
std::cin >> x;
out[x] = true;
st.push(x);
}
if(y>=RANGE){
for(int i=1;i<=n;i++) dp[i] = -1e18;
dp[t]=0;
int ans = -1;
if(!out[t]) ans = 0;
for(int i = t-1;i >= 1;i--)
{
for(int v : adj[i]) dp[i] = std::max(dp[i],dp[v]+1);
if(!out[i]) ans = std::max(ans,dp[i]);
}
std::cout << ans << '\n';
}
else{
int ans = -1;
for(auto [x,y] : res[t]) if(!out[x]){ ans = y; break; }
std::cout << ans << '\n';
}
while(!st.empty()) out[st.top()] = false,st.pop();
}
}