Submission #1093805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093805		quannnguyen2009	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1837 ms	114260 KiB

bitaro

#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, inf = 1e18;

int n, m, q, block;
int vis[N];
bool del[N];
int dp[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;
    block = 100;
    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();
    }
}

Compilation message (stderr)

bitaro.cpp:11:39: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   11 | const int N=1e5+5, mod = 1e9+7, inf = 1e18;
      |                                       ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86