Submission #697708

#	Time	Username	Problem	Language	Result	Execution time	Memory
697708		bebra	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1575 ms	218292 KiB

bitaro

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

#define dbg(x) cerr << #x << ": " << x << endl;

const int MAX_N = 1e5 + 5;
const int MAX_K = 150;
const int INF = 1e9;
vector<int> g[MAX_N];
vector<int> gt[MAX_N];
bool block[MAX_N];
int used[MAX_N];
vector<pair<int, int>> paths[MAX_N];


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        gt[v].push_back(u);
    }
    fill_n(used, MAX_N, -1);
    for (int v = 0; v < n; ++v) {
        for (auto u : gt[v]) {
            for (const auto& [u1, x] : paths[u]) {
                if (used[u1] == -1) {
                    used[u1] = paths[v].size();
                    paths[v].emplace_back(u1, x + 1);
                } else {
                    paths[v][used[u1]].second = max(paths[v][used[u1]].second, x + 1);
                }
            }
            sort(paths[v].rbegin(), paths[v].rend(), [&](const auto& lhs, const auto& rhs) {
                return tie(lhs.second, lhs.first) < tie(rhs.second, rhs.first);
            });
            while (paths[v].size() > MAX_K) {
                used[paths[v].back().first] = -1;
                paths[v].pop_back();
            }
            for (int i = 0; i < (int)paths[v].size(); ++i) {
                const auto& [u1, x] = paths[v][i];
                used[u1] = i;
            }
        }
        if (paths[v].size() < MAX_K) {
            paths[v].emplace_back(v, 0);
        }
        for (const auto& [u, x] : paths[v]) {
            used[u] = -1;
        }
    }
    while (q--) {
        int s;
        cin >> s;
        --s;
        int k;
        cin >> k;
        int res = -INF;
        vector<int> curr(k);
        for (int i = 0; i < k; ++i) {
            int v;
            cin >> v;
            --v;
            curr[i] = v;
            block[v] = true;
       }
        if (k >= MAX_K) {
            vector<int> dp(n, -INF);
            dp[s] = 0;
            for (int v = s - 1; v >= 0; --v) {
                for (auto u : g[v]) {
                    if (dp[u] == -INF) continue;
                    dp[v] = max(dp[v], dp[u] + 1);
                }
            }
            for (int v = 0; v < n; ++v) {
                if (block[v]) continue;
                res = max(res, dp[v]);
            }
        } else {
            for (const auto& [v, x] : paths[s]) {
                if (block[v]) continue;
                res = max(res, x);
            }
        }
        if (res == -INF) {
            cout << "-1\n";
        } else {
            cout << res << '\n';
        }
        for (auto v : curr) {
            block[v] = false;
        }
    }
    return 0;
}

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