Submission #954962

#TimeUsernameProblemLanguageResultExecution timeMemory
954962ByeWorldBitaro’s Party (JOI18_bitaro)C++14
7 / 100
2067 ms34308 KiB
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define md ((l+r)>>1)
#define lf (id<<1)
#define rg ((id<<1)|1)
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<pii,ll> ipii;
const int MAXN = 3e5+10;
const ll INF = 2e18+10;
const ll LOG = 61;
const int SQRT = 1e5+10;
const int MOD = 998244353;

int n, m, q;
vector <int> adj[MAXN];
vector <pii> best[MAXN], que;
vector <int> vec[MAXN];
int ans;
int busy[MAXN], vis[MAXN];
int day, day2;

void dfs(int nw, int dis){
    if(busy[nw] != day) ans = max(ans, dis);
    vis[nw] = day2;
    for(auto nx : adj[nw]){
        if(vis[nx] != day2) dfs(nx, dis+1);
    }
}
signed main() {
	cin >> n >> m >> q;
	for(int i=1; i<=m; i++){
        int u, v; cin >> u >> v;
        adj[v].pb(u);
    }
    for(int i=1; i<=n; i++){
        vector <pii> coba;
        coba.pb({0, i});
        for(auto nx : adj[i]){
            for(auto in : best[nx]) coba.pb({in.fi+1, in.se});
        }
        sort(coba.rbegin(), coba.rend());
        
        day++;
        for(auto in : coba){
            if(busy[in.se] == day) continue;
            busy[in.se] = day;
            best[i].pb(in);
            if(best[i].size() == SQRT) break;
        }
    }
    // for(int i=1; i<=n; i++){
    //     cout << "\ni" << i << "\n";
    //     for(auto in:best[i]) cout << in.fi << ' ' << in.se << '\n';
    // }
    // exit(0);
    for(int i=1; i<=q; i++){
        int sta, siz; cin >> sta >> siz;
        ans = -1;
        for(int j=0; j<siz; j++){
            int x; cin >> x;
            vec[i].pb(x);
        }
        if(siz >= SQRT){
            day++; day2++;
            for(auto in : vec[i]) busy[in] = day;
            dfs(sta, 0);
        } else {
            day++;
            for(auto in : vec[i]) busy[in] = day;
            for(auto in : best[sta]){
                if(busy[in.se] == day) continue;
                ans = in.fi;
                break;
            }
        }
        cout << ans << '\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...