Submission #1093808

#TimeUsernameProblemLanguageResultExecution timeMemory
1093808vjudge1Bitaro’s Party (JOI18_bitaro)C++17
100 / 100
1858 ms114256 KiB
#include<bits/stdc++.h>
// #define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;
 
const int N=1e5+5, mod = 1e9+7, block = 100;
 
int n, m, q, vis[N], dp[N];
bool del[N];
vector<int> lst, adj[N];
vector<ii> rnk[N];
 
void clr(priority_queue<ii>& pq) { while(sz(pq)) pq.pop(); }
 
void pre() {
    priority_queue<ii> pq;
    for (int i=1; i<=n; i++) {
        pq.push({0, i});
        for (int u: adj[i]) {
            for (auto [v, d]: rnk[u]) pq.push({d+1, v});
        }
        while(sz(rnk[i])<block && sz(pq)) {
            auto [d, u] = pq.top(); pq.pop();
            if(vis[u]!=i) {
                vis[u] = i;
                rnk[i].pb({u, d});
            }
        }
        clr(pq);
    }
}
 
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> q;
    for (int i=1; i<=m; i++) {
        int u, v; cin >> u >> v;
        adj[v].pb(u);
    }
    pre();
    while(q--) {
        int t, y; cin >> t >> y;
        for (int i=1; i<=y; i++) {
            int tmp; cin >> tmp;
            lst.pb(tmp); del[tmp] = 1; 
        }
        if(y>=block) {
            for (int i=1; i<=t; i++) {
                if(del[i]) dp[i] = -1;
                else dp[i] = 0;
                for (int u: adj[i]) {
                    if(dp[u]!=-1) dp[i] = max(dp[i], dp[u]+1);
                }
            }
            cout << dp[t] << '\n';
        } else {
            bool b = 1;
            for (auto [u, d]: rnk[t]) {
                if(!del[u]) {
                    cout << d << '\n';
                    b = 0; break;
                }
            }
            if(b) cout << -1 << '\n';
        }
        for (auto it: lst) del[it] = 0;
        lst.clear();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...