Submission #1241084

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241084		duckindog	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	1667 ms	547320 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10,
            S = 300;
int n, m, q;
vector<int> ad[N], rAd[N];
int deg[N];

bool isBan[N], mk[N];

vector<pair<int, int>> fB[N];
int fS[N];

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m >> q;
    for (int i = 1; i <= m; ++i) { 
        int u, v; cin >> u >> v;
        ad[u].push_back(v);
        rAd[v].push_back(u);
    }

    vector<int> order;
    { // toposort
        for (int u = 1; u <= n; ++u) { 
            for (const auto& v : ad[u]) deg[v] += 1;
        }
        queue<int> q;
        for (int i = 1; i <= n; ++i) if (!deg[i]) q.push(i);
        while (q.size()) { 
            auto u = q.front(); q.pop();
            order.push_back(u);
            for (const auto& v : ad[u]) { 
                if (!--deg[v]) q.push(v);
            }
        }
    }

    for (int i = 1; i <= n; ++i) fB[i].push_back({-1, i});
    for (const auto& u : order) { 
        { // sort fB[u]
            vector<pair<int, int>> tmp = fB[u];
            fB[u].clear();
            stable_sort(tmp.begin(), tmp.end(), greater<>());
            
            for (const auto& [dist, v] : tmp) {
                if (mk[v]) continue;
                fB[u].push_back({dist + 1, v}); 
                mk[v] = true;
                if ((int)fB[u].size() > S) break;
            }
            for (const auto& [dist, v] : fB[u]) mk[v] = false;
        }
        
        for (const auto& v : ad[u]) { 
            fB[v].insert(fB[v].end(), fB[u].begin(), fB[u].end());
        }
    }

    reverse(order.begin(), order.end());
    while (q--) { 
        int x, k; cin >> x >> k;
        vector<int> banList(k);
        for (auto& v : banList) cin >> v, isBan[v] = true;

        int answer = -1;
        if (k > S) { 
            fill(fS + 1, fS + n + 1, -1'000'000);
            fS[x] = 0;
            for (const auto& u : order) { 
                for (const auto& v : rAd[u]) fS[v] = max(fS[v], fS[u] + 1);
                if (!isBan[u]) answer = max(answer, fS[u]);
            }
        } else { 
            for (const auto& [dist, v] : fB[x]) {
                if (!isBan[v]) answer = max(answer, dist);
            }
        }
        cout << answer << "\n";

        for (const auto& v : banList) isBan[v] = false;
    }
}

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