Submission #331251

#	Time	Username	Problem	Language	Result	Execution time	Memory
331251		12tqian	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1609 ms	415456 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;

int main() {
    const int B = 350;
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[v].push_back(u);
        // REVERSED EDGES
    }
    vector<vector<pair<int, int>>> far(n); // Store furthest B cities, pair of vertex and distance (sorted by distance)
    vector<int> done(n);
    vector<pair<int, int>> res;
    auto merge = [&](vector<pair<int, int>>& a, vector<pair<int, int>>& b) {
        res.clear();
        int ia = 0;
        int ib = 0;
        int sa = (int) a.size();
        int sb = (int) b.size();
        for (auto x : a)
            done[x.second] = 0;
        for (auto x : b)
            done[x.second] = 0;
        while ((ia < sa || ib < sb) && (int) res.size() <= B) {
            if (ia == sa) {
                if (!done[b[ib].second])
                    res.emplace_back(b[ib].first + 1, b[ib].second);
                done[b[ib].second] = 1;
                ib++;
            } else if (ib == sb) {
                if (!done[a[ia].second])
                    res.push_back(a[ia]);
                done[a[ia].second] = 1;
                ia++;
            } else if(a[ia].first > b[ib].first + 1) {
                if (!done[a[ia].second])
                    res.push_back(a[ia]);
                done[a[ia].second] = 1;
                ia++;
            } else {
                if (!done[b[ib].second])
                    res.emplace_back(b[ib].first + 1, b[ib].second);
                done[b[ib].second] = 1;
                ib++;
            }
        }
        a.swap(res);
    };
    for (int i = 0; i < n; i++) {
        auto& cur = far[i];
        cur = {{0, i}};
        for (int j : adj[i]) {
            merge(cur, far[j]);
        }
    }
    vector<int> big(n);
    vector<int> dist(n, -1);
    auto compute_dist = [&](int src) -> int {
        for (int i = 0; i < src; i++)
            dist[i] = -1;
        dist[src] = 0;
        for (int i = src; i >= 0; i--) {
            if (dist[i] == -1)
                continue;
            for (int j : adj[i]) {
                dist[j] = max(dist[j], dist[i] + 1);
            }
        }
        int mx = -1;
        for (int i = 0; i <= src; i++) {
            if (big[i]) 
                continue;
            mx = max(mx, dist[i]);
        }
        return mx;
    };
    vector<int> bad;
    while (q--) {
        int t, y; 
        cin >> t >> y;
        t--;
        bad.resize(y);
        for (int i = 0; i < y; i++) 
            cin >> bad[i], bad[i]--;
        for (int x : bad)
            big[x] = 1;
        if (y >= B) {
            int ans = compute_dist(t);
            cout << ans << '\n';
        } else {
            // We store the sqrt furthest paths away from every vertex
            // To do that we can 
            int ans = -1;
            for (auto x : far[t]) {
                if (big[x.second]) 
                    continue;
                ans = max(ans, x.first);
            }
            cout << ans << '\n';
        }
        for (int x : bad)
            big[x] = 0;
    }
    return 0;
}

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