Submission #1132091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132091		AndrijaM	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	750 ms	152732 KiB

bitaro

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#include <set>

using namespace std;
using ll = long long;
using vl = vector<ll>;

// Overload input operator for vector
istream &operator>>(istream &is, vl &a) {
    for (auto &x : a) cin >> x;
    return is;
}

constexpr int MAX_NODES = 200200;
constexpr int BLOCK_SIZE = 100;
vector<int> forwardGraph[MAX_NODES], reverseGraph[MAX_NODES];

// Function to process least arrays for all nodes
void preprocessLeastArrays(int n, vector<vector<pair<int, int>>> &least) {
    vector<int> used(n + 1, -1);
    least[1] = {{0, 1}};

    for (int i = 2; i <= n; i++) {
        vector<int> tempStorage;

        // Traverse reverse edges
        for (auto &neighbor : reverseGraph[i]) {
            for (auto &[dist, node] : least[neighbor]) {
                if (used[node] < 0) tempStorage.push_back(node);
                used[node] = max(used[node], dist + 1);
            }
        }

        // Update least array for node `i`
        least[i].emplace_back(0, i);
        for (auto &x : tempStorage) {
            least[i].emplace_back(used[x], x);
        }

        // Sort and trim to BLOCK_SIZE
        sort(least[i].begin(), least[i].end(), greater<>());
        if (least[i].size() > BLOCK_SIZE) {
            least[i].resize(BLOCK_SIZE);
        }

        // Reset `used` array
        for (auto &x : tempStorage) {
            used[x] = -1;
        }
    }
}

// Function to handle queries
void handleQuery(int t, int y, const vector<int> &blocked, 
                 const vector<vector<pair<int, int>>> &least) {
    set<int> blockedSet(blocked.begin(), blocked.end());

    if (y >= BLOCK_SIZE) {
        // Dynamic programming for large number of blocked nodes
        vector<int> dp(t + 1, -1);
        dp[t] = 0;

        for (int node = t; node >= 1; node--) {
            if (dp[node] == -1) continue;
            for (const auto &neighbor : reverseGraph[node]) {
                dp[neighbor] = max(dp[neighbor], dp[node] + 1);
            }
        }

        int maxDistance = -1;
        for (int node = 1; node <= t; node++) {
            if (!blockedSet.count(node)) {
                maxDistance = max(maxDistance, dp[node]);
            }
        }

        cout << maxDistance << "\n";
    } else {
        // Direct computation for small number of blocked nodes
        int maxDistance = -1;
        for (const auto &[dist, node] : least[t]) {
            if (!blockedSet.count(node)) {
                maxDistance = max(maxDistance, dist);
            }
        }

        cout << maxDistance << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;

    // Input graph edges
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        forwardGraph[u].push_back(v);
        reverseGraph[v].push_back(u);
    }

    // Prepare least arrays for all nodes
    vector<vector<pair<int, int>>> least(n + 1);
    preprocessLeastArrays(n, least);

    // Process queries
    for (int i = 0; i < q; i++) {
        int t, y;
        cin >> t >> y;

        vector<int> blocked(y);
        for (int j = 0; j < y; j++) {
            cin >> blocked[j];
        }

        handleQuery(t, y, blocked, least);
    }

    return 0;
}

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