| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1220677 | ssafarov | Bitaro’s Party (JOI18_bitaro) | C++20 | 0 ms | 0 KiB |
#define Magic ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll int
#define ld long long double
#define en '\n'
#define tsts int tetss; cin >> tetss; while(tetss--)
#define all(a) a.begin() , a.end()
#define pb push_back
#define ld long long double
#define fi first
#define se second
ll INF = 1e18;
const int N = 2e5 + 1;
const int mod = 998244353;
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// order_of_key(n) - The number of items in a set that are strictly smaller than k
// find_by_order(k) - It returns an iterator to the ith largest element
ll lcm(ll a, ll b)
{
ll gc = __gcd(a, b);
return a / gc * b;
}
ll binpow (ll a, ll n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return binpow (a, n-1) * a;
else {
ll b = binpow (a, n/2);
return b * b;
}
}
ll binpow_mod(ll a, ll b, ll md)
{
ll res = 1;
a = a % md;
while (b > 0)
{
if (b & 1)
res = (res * a) % md;
a = (a * a) % md;
b >>= 1;
}
return res;
}
ll in() {ll x; cin >> x; return x;};
ll gcd (ll a, ll b, ll & x, ll & y) {
if (a == 0) {
x = 0; y = 1;
return b;
}
ll x1, y1;
ll d = gcd (b%a, a, x1, y1);
x = y1 - (b / a) * x1;
y = x1;
return d;
}
ll gcdinv(ll a, ll b){
ll x, y;
gcd(a, b, x, y);
return x;
}
ll eql(ll x, ll y, bool ok){
if(ok) return x;
else return y;
}
// -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- чё
vector<vector<ll>> v(N);
vector<vector<ll>> rv(N);
vector<vector<pair<ll,ll>>> ch(N);
vector<ll> tps;
ll k;
ll us[N];
ll nus[N];
void dfs(ll x){
us[x] = 1;
for(auto g : v[x]){
if(!us[g])dfs(g);
}
tps.pb(x);
}
void func(ll x){
ll sz = rv[x].size();
ll cur[sz] = {};
for(ll i = 1; i <= k; ++i){
ll fs = -1;
ll sc = -1;
for(ll j = 0; j < sz; ++j){
ll y = rv[x][j];
ll rsz = ch[y].size();
while(cur[j] != rsz){
ll z1 = ch[y][cur[j]].fi;
ll z2 = ch[y][cur[j]].se;
if(nus[z2] == x){
cur[j]++;
continue;
}
if(z1 >= fs){
cur[j]++;
fs = z1 + 1;
sc = z2;
}
break;
}
}
if(sc == -1) break;
nus[sc] = x;
ch[x].pb({fs, sc});
}
if((ll)ch[x].size() < k) ch[x].pb({0, x});
}
void solve(){
ll n, m, q; cin >> n >> m >> q;
for(ll i = 1; i <= m; ++i){
ll x, y; cin >> x >> y;
v[x].pb(y);
rv[y].pb(x);
}
k = min(340ll, n);
for(ll i = 1; i <= n; ++i){
if(us[i]) continue;
dfs(i);
}
reverse(all(tps));
for(auto g : tps){
func(g);
}
for(ll i = 1; i <= q; ++i){
ll x, sk; cin >> x >> sk;
if(sk < k){
set<ll> ban;
for(ll i = 1; i <= sk; ++i){
ll ck; cin >> ck;
ban.insert(ck);
}
ll cans = -1;
for(auto g : ch[x]){
if(ban.find(g.se) != ban.end()) continue;
cans = g.fi;
break;
}
cout << cans << en;
}else{
ll ban[n+12] = {};
for(ll i = 1; i <= sk; ++i){
ll ch; cin >> ch;
ban[ch] = 1;
}
ll tms[n+12] = {};
ll mx[n+12] = {};
for(ll i = 1; i <= n; ++i) mx[i] = -1;
mx[x] = 0;
vector<ll> svo;
for(ll i = 1; i <= n; ++i) svo.pb(i);
queue<ll> bfs;
bfs.push(x);
ll cans = -1;
while(bfs.size() or svo.size()){
ll ch;
if(bfs.size()){
ch = bfs.front();
}else{
while(svo.size()){
if(tms[svo.back()] == (ll)v[svo.back()].size()){
svo.pop_back();
continue;
}
bfs.push(svo.back());
svo.pop_back();
break;
}
continue;
}
if(!ban[ch])cans = max(cans, mx[ch]);
bfs.pop();
if(mx[ch] >= 0)for(auto g : rv[ch]){
tms[g]++;
mx[g] = max(mx[g], mx[ch] + 1);
if(tms[g] == (ll)v[g].size()){
bfs.push(g);
}
}
}
cout << cans << en;
}
}
}
int main(){
// freopen("fairphoto.in", "r", stdin); freopen("fairphoto.out", "w", stdout);
Magic
// tsts{
solve();
cout << endl;
// }
}