| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1316675 | aaaaaaaa | Bitaro’s Party (JOI18_bitaro) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
const int mxN = 2e5 + 100;
const int mxB = 343;
vector<pair<int, int>> path[mxN];
vector<int> adj[mxN], radj[mxN];
signed main(){
ios::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
vector<int> mn(n + 1, -1), vis(n + 1, 0), dp(n + 1, -1);
for(int i = 0, u, v; i < m; ++i){
cin >> u >> v; --u, --v;
adj[u].push_back(v);
radj[v].push_back(u);
}
for(int i = 0; i < n; ++i){
path[i].push_back({i, 0});
vector<int> all_node;
for(auto it : radj[i]){
for(auto [v, w] : path[it]){
if(mn[v] == -1){
all_node.push_back(v);
mn[v] = w + 1;
}else if(mn[v] < w + 1){
mn[v] = w + 1;
}
}
}
for(auto it : all_node){
path[i].push_back({it, mn[it]});
}
sort(all(path[i]), [&](pair<int, int> p1, pair<int, int> p2){
return p1.second > p2.second;
});
while(path[i].size() > mxB) path[i].pop_back();
for(auto it : all_node) mn[it] = -1;
}
while(q--){
int x, y;
cin >> x >> y;
--x;
vector<int> ban;
for(int j = 0; j < n; ++j) vis[j] = 0;
while(y--){
int u;
cin >> u;
--u;
vis[u] = 1;
ban.push_back(u);
}
if((int) ban.size() >= (int) path[i].size()){
priority_queue<pair<int, int>> pq;
int ans = -1;
pq.push({0, x}), dp[x] = 0;
while(pq.size()){
auto [w, u] = pq.top();
pq.pop();
for(auto it : radj[u]){
if(dp[it] < w + 1){
dp[it] = w + 1;
pq.push({dp[it], it});
}
}
}
for(int j = 0; j <= x; ++j){
if(!vis[j]) ans = max(ans, dp[j]);
dp[j] = -1;
}
cout << ans << "\n";
}else{
int ans = -1;
for(auto [u, w] : path[x]){
if(vis[u] == 0){
ans = max(ans, w);
}
}
cout << ans << "\n";
}
for(auto it : ban) vis[it] = 0;
}
return 0;
}