| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1344365 | jump | Bitaro’s Party (JOI18_bitaro) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define int long long
int RANGE=100000;
int n,m,q;
int height[100010];
std::vector<std::pair<int,int>> dpV[100010];
int dp[100010];
int tempDp[100010];
std::vector<int> adj[100010];
std::vector<int> order;
bool visit[100010];
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::cin >> n >> m >> q;
RANGE=std::sqrt(100000);
for(int i=0;i<m;i++){
int s,e;
std::cin >> s >> e;
adj[s].push_back(e);
}
for(int i=1;i<=n;i++){
dpV[curr].reserve(RANGE);
dfs(i);
}
std::reverse(order.begin(),order.end());
for(auto curr:order){
dpV[curr].push_back({0,curr});
std::sort(dpV[curr].rbegin(),dpV[curr].rend());
while(dpV[curr].size()>RANGE)dpV[curr].pop_back();
for(auto to:adj[curr]){
for(auto [value,from]:dpV[curr]){
dpV[to].push_back({value+1,from});
}
dpV[to].push_back({1,curr});
dp[to]=std::max(dp[to],dp[curr]+1);
}
}
while(q--){
int t,y;
std::vector<int> absent;
std::cin >> t >> y;
if(y==0){
std::cout << dp[t] << '\n';
continue;
}
for(int i=0;i<y;i++){
int yin;
std::cin >> yin;
absent.push_back(yin);
}
int ans=-1;
for(auto [num,from]:dpV[t]){
auto itr = std::lower_bound(absent.begin(),absent.end(),from);
if(itr==absent.end()||*itr!=from){
ans = num;
break;
}
}
if(ans!=-1){
std::cout << ans << '\n';
continue;
}
for(int i=1;i<=n;i++){
auto itr = std::lower_bound(absent.begin(),absent.end(),i);
if(itr==absent.end()||*itr!=i)
tempDp[i]=0;
else
tempDp[i]=-1e9;
}
for(auto curr:order){
for(auto to:adj[curr]){
tempDp[to]=std::max(tempDp[to],tempDp[curr]+1);
}
}
tempDp[t]=std::max((int)(-1),tempDp[t]);
std::cout << tempDp[t] << '\n';
}
}