Submission #1134954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134954		minhnguyent546	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	7 ms	4168 KiB

bitaro

/**            
 * author      minhnguyent546
 * created_at  Sat, 2025-01-11 17:02:51
 * problem     https://oj.uz/problem/view/JOI18_bitaro
 **/           
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "cp/debug.h"
#else
#define debug(...)
#define cerr if (false) cerr
#endif

const int INF = 0x3f3f3f3f;

#ifdef LOCAL
const int thetaparacetamol = 1;
#else
const int thetaparacetamol =                        499;
#endif

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> g(n);
    vector<vector<int>> h(n);
    vector<int> out_deg(n), in_deg(n);
    vector<int> zero_out_deg_vers;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        assert(u < v);
        g[u].emplace_back(v);
        h[v].emplace_back(u);
        out_deg[u]++;
        in_deg[v]++;
    }

    for (int i = 0; i < n; ++i) {
        if (out_deg[i] == 0) {
            zero_out_deg_vers.emplace_back(i);
        }
    }

    vector<vector<pair<int, int>>> furthest(n); // (ver, dist)
    for (int i = 0; i < n; ++i) {
        furthest[i].emplace_back(i, 0);
    }

    {
        vector<int> dp(n);
        vector<int> que;
        for (int i = 0; i < n; ++i) {
            if (in_deg[i] == 0) {
                que.emplace_back(i);
            }
        }

        vector<bool> seen(n);
        for (int k = 0; k < (int) que.size(); ++k) {
            int me = que[k];
            int my_size = (int) furthest[me].size();
            // cerr << "me = " << me + 1 << '\n';
            for (int his : g[me]) {
                vector<pair<int, int>> new_vers;
                int my_ptr = 0, his_ptr = 0;
                int his_size = (int) furthest[his].size();
                while (my_ptr < my_size || his_ptr < his_size) {
                    if (his_ptr == his_size || (my_ptr < my_size && furthest[me][my_ptr].second + 1 > furthest[his][his_ptr].second)) {
                        if (!seen[furthest[me][my_ptr].first]) {
                            new_vers.emplace_back(furthest[me][my_ptr].first, furthest[me][my_ptr].second + 1);
                            seen[furthest[me][my_ptr].first] = true;
                        }
                        ++my_ptr;
                    } else {

                        if (!seen[furthest[his][his_ptr].first]) {
                            new_vers.emplace_back(furthest[his][his_ptr].first, furthest[his][his_ptr].second);
                            seen[furthest[his][his_ptr].first] = true;
                        }
                        ++his_ptr;
                    }
                    if ((int) new_vers.size() == thetaparacetamol + 1) break;
                }

                for (auto [z, _] : new_vers) {
                    seen[z] = false;
                }
                furthest[his].swap(new_vers);

                if (--in_deg[his] == 0) {
                    que.emplace_back(his);
                }
                // cerr << "me = " << me + 1 << ", his = " << his + 1 << ", in_deg[his] = " << in_deg[his] << '\n';
            }
        }
    }


    vector<bool> go_out(n);
    vector<int> vers(n);
    vector<int> dp(n);

    #ifdef LOCAL
        for (int ver = 0; ver < n; ++ver) {
            cerr << "ver = " << ver + 1 << ": ";
            for (auto [v, dist] : furthest[ver]) {
                cerr << "(" << v + 1 << ", " << dist << ")" << ' ';
            }
            cerr << '\n';
        }
    #endif

    for (int w = 0; w < q; ++w) {
        int ver, num_vers;
        cin >> ver >> num_vers;
        --ver;
        for (int i = 0; i < num_vers; ++i) {
            int v;
            cin >> v;
            --v;
            vers[i] = v;
            go_out[v] = true;
        }

        if (num_vers > thetaparacetamol) {
            fill(dp.begin(), dp.begin() + ver + 1, 0);
            dp[ver] = 0;
            auto cur_out_deg = out_deg;
            vector<int> que = zero_out_deg_vers;
            for (int k = 0; k < (int) que.size(); ++k) {
                int u = que[k];
                if (u == ver) continue;
                for (int v : h[u]) {
                    --cur_out_deg[v];
                    if (v == ver) continue;
                    if (cur_out_deg[v] == 0) {
                        que.emplace_back(v);
                    }
                }
            }
            assert(cur_out_deg[ver] == 0);
            que = {ver};
            for (int k = 0; k < (int) que.size(); ++k) {
                int u = que[k];
                for (int v : h[u]) {
                    dp[v] = max(dp[v], dp[u] + 1);
                    if (--cur_out_deg[v] == 0) {
                        que.emplace_back(v);
                    }
                }
            }

            int ans = -1;
            for (int i = 0; i <= ver; ++i) {
                if (go_out[i]) continue;
                ans = max(ans, dp[i]);
            }

            cout << ans << '\n';
        } else {
            int ans = -1;
            
            for (int i = 0; i < (int) furthest[ver].size(); ++i) {
                if (!go_out[i]) {
                    ans = furthest[ver][i].second;
                    break;
                }

            }
            cout << ans << '\n';
        }   

        // reset
        for (int i = 0; i < num_vers; ++i) {
            go_out[vers[i]] = false;
        }
    }
    
    return 0;
}

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