Submission #331236

#	Time	Username	Problem	Language	Result	Execution time	Memory
331236		12tqian	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	21 ms	7788 KiB

bitaro

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

int main() {
    const int B = 505;
    const int INF = 1e9;
    // 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)
    auto merge = [&](vector<pair<int, int>>& a, vector<pair<int, int>>& b) {
        vector<pair<int, int>> res;
        int ia = 0;
        int ib = 0;
        int sa = (int) a.size();
        int sb = (int) b.size();
        while (ia < sa || ib < sb) {
            if (ia == sa) {
                res.emplace_back(b[ib].first + 1, b[ib].second);
                ib++;
            } else if (ib == sb) {
                res.push_back(a[ia]);
                ia++;
            } else if(a[ia].first > b[ib].first + 1) {
                res.push_back(a[ia]);
                ia++;
            } else {
                res.emplace_back(b[ib].first + 1, b[ib].second);
                ib++;
            }
        }
        a.clear();
        for (int i = 0; i < (int) res.size(); i++) {
            if (i != (int) res.size() - 1 && res[i] == res[i + 1])
                continue;
            a.push_back(res[i]);
        }
        while ((int) a.size() > B) 
            a.pop_back();
    };
    for (int i = 0; i < n; i++) {
        auto& cur = far[i];
        cur = {{0, i}};
        for (int j : adj[i]) {
            merge(cur, far[j]);
        }
    }
    auto compute_dist = [&](int src, vector<int>& bad) -> int {
        // Return furthest city not in bad
        vector<int> dist(n, -1);
        vector<int> avoid(n);
        for (int x : bad)
            avoid[x] = 1;
        dist[src] = 0;
        for (int i = src; i >= 0; i--) {
            for (int j : adj[i]) {
                dist[j] = max(dist[j], dist[i] + 1);
            }
        }
        int mx = -1;
        for (int i = 0; i < n; i++) {
            if (avoid[i]) 
                continue;
            mx = max(mx, dist[i]);
        }
        return mx;
    };
    vector<int> big(n);
    while (q--) {
        int t, y; 
        cin >> t >> y;
        t--;
        vector<int> bad(y);
        for (int i = 0; i < y; i++) 
            cin >> bad[i], bad[i]--;
        set<int> check;
        for (int x : bad)
            big[x] = 1;
        if (y >= B) {
            int ans = compute_dist(t, bad);
            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;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:6:15: warning: unused variable 'INF' [-Wunused-variable]
    6 |     const int INF = 1e9;
      |               ^~~

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