| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1054556 | Minbaev | Bitaro’s Party (JOI18_bitaro) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define f first
#define s second
#define pii pair<int,int>
#define ar array
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
template<class T> using st = tree<T, null_type, less_equal<T>,
rb_tree_tag, tree_order_statistics_node_update>;
const int inf = 1e17 + 7;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
const int md = 998244353;
int binpow(int a, int b){
if(b == 0)return 1;
if(b % 2 == 0){
int c = binpow(a,b/2);
return (c*c)%mod;
}
return (binpow(a,b-1)*a)%mod;
}
int divi(int a, int b){
return (a*(binpow(b,mod-2)))%mod;
}
int n,m,k;
const int sz = 300;
vector<int>g[N], gg[N];
vector<pii>calc[N];
void solve(){
int q;
cin >> n >> m >> q;
while(m--){
int a,b;
cin >> a >> b;
g[a].pb(b);
gg[b].pb(a);
}
vector<int> reach, dist(n+1), last(n+1, 0);
for(int i = 1;i <= n; i++){
reach.push_back(i);
for(auto to : gg[i]){
for(auto [d, u] : calc[to]){
if(last[u] == i){
dist[u] = max(dist[u], d + 1);
}else{
dist[u] = d + 1;
last[u] = i;
reach.push_back(u);
}
}
}
sort(all(reach),[&](int a, int b){
return dist[a] > dist[b];
});
for(int j = 0;j < min(sz, (int)reach.size()); j++){
calc[i].push_back({dist[reach[j]], reach[j]});
}
reach.clear();
}
int timer = 1;
vector<int> del(n+1, 0);
while(q--){
int v, k; cin >> v >> k;
for(int i = 0;i < k; i++){
int x; cin >> x;
del[x] = timer;
}
if(k < sz){
int ans = -1;
for(auto [d, u] : calc[v]){
if(del[u] != timer){
ans = d;
break;
}
}
cout << ans << '\n';
}else{
vector<int> d(n+1, -1);
for(int i = 1;i <= n; i++){
if(del[i] != timer){
d[i] = max(d[i], 0ll);
}
for(int to : g[i]){
if(d[i] != -1)
d[to] = max(d[to], d[i] + 1);
}
}
cout << d[v] << '\n';
}
timer++;
}
}
/*
5 6 1
5 3
5 4
3 1
3 2
4 2
2 1
2 1 5
1 2 3 4
4 3 1 2 5
*/
signed main()
{
// freopen("seq.in", "r", stdin);
// freopen("seq.out", "w", stdout);
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int tt=1;//cin>>tt;
while(tt--)solve();
}