제출 #958444

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
958444		MisterReaper	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	1519 ms	416648 KiB

bitaro

#include <bits/stdc++.h>
using i64 = long long;

constexpr int maxN = 1E5 + 5;

std::vector<int> prev[maxN], val(maxN, -1), vis(maxN, -1);
std::vector<std::pair<int, int>> save[maxN];

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

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

    for(int i = 0; i < m; i++) {
        int u, v;
        std::cin >> u >> v;
        prev[--v].emplace_back(--u);
    }

    constexpr int S = 350;

    for(int i = 0; i < n; i++) {
        std::vector<int> all{i};
        val[i] = 0;
        for(int u : prev[i]) {
            for(auto [d, v] : save[u]) {
                if(vis[v] != i) {
                    all.emplace_back(v);
                    val[v] = d + 1;
                } else {
                    val[v] = std::max(val[v], d + 1);
                }
            }
        }

        std::sort(all.begin(), all.end(), [&](int lhs, int rhs) -> bool {
            return val[lhs] > val[rhs];
        });

        for(int j = 0; j < std::min(int(all.size()), S); j++) {
            save[i].emplace_back(val[all[j]], all[j]);
        }
    }

    for(int _ = 0; _ < q; _++) {
        int t, y; 
        std::cin >> t >> y;
        std::set<int> ban;
        for(int i = 0, x; i < y; i++) {
            std::cin >> x;
            ban.emplace(x - 1);
        }

        if(y >= S) {
            std::vector<int> dp(t, -1);
            dp[t - 1] = 0;
            for(int i = t - 1; i >= 0; i--) {
                if(dp[i] == -1) {
                    continue;
                }
                for(int u : prev[i]) {
                    dp[u] = std::max(dp[u], dp[i] + 1);
                }
            }

            int ans = -1;
            for(int i = 0; i < t; i++) {
                if(!ban.count(i)) {
                    ans = std::max(ans, dp[i]);
                }
            }
            std::cout << ans << "\n";
        } else {
            int ans = -1;
            for(auto [d, v] : save[t - 1]) {
                if(!ban.count(v)) {
                    ans = d;
                    break;
                }
            }
            std::cout << ans << "\n";
        }
    }

    return 0;
}

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