제출 #1127639

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127639		moonpay	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	7 ms	9848 KiB

bitaro

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#include <set>

using namespace std;
using ll = long long;
using vl = vector<ll>;

istream &operator>>(istream &os, vl &a) {
    for (auto &x: a) cin >> x;
    return os;
}

constexpr int N = 200200;
constexpr int B = 150;
vector<int> g[N], ig[N];

signed 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 s, e;
        cin >> s >> e;
        g[s].push_back(e);
        ig[e].push_back(s);
    }
    std::vector<std::vector<pair<int, int> > > least(n + 1, std::vector<pair<int, int> >());
    std::vector<bool> used(n + 1, false);
    least[1] = {{0, 1}};
    for (int i = 2; i <= n; i++) {
        vector<int> free;
        std::vector<int> can;
        std::vector<int> sz;
        for (const auto &d: ig[i]) {
            can.push_back(d);
            sz.push_back(least[d].size());
        }
        std::vector<int> ind(sz.size(), 0);
        for (int j = 0; j < B; j++) {
            int mx = -1;
            int where = -1;
            for (int id = 0; id < sz.size(); id++) {
                while (ind[id] < sz[id] && used[least[can[id]][ind[id]].second]) {
                    ind[id]++;
                }
            }
            for (int id = 0; id < sz.size(); id++) {
                if (ind[id] < sz[id] && least[can[id]][ind[id]].first > mx) {
                    mx = least[can[id]][ind[id]].first;
                    where = least[can[id]][ind[id]].second;
                }
            }
            if (where == -1) {
                break;
            } else {
                used[where] = true;
                free.push_back(where);
                ind[where]++;
                least[i].emplace_back(mx + 1, where);
            }
        }

        if (least[i].size() < B) {
            least[i].emplace_back(0, i);
        }
        for (auto &d: free) used[d] = false;
    }
    for (int i = 0; i < q; i++) {
        int t, y;
        cin >> t >> y;
        vector<int> blocked(y);
        std::set<int> bl;
        for (int j = 0; j < y; j++) {
            cin >> blocked[j];
            bl.insert(blocked[j]);
        }
        if (y >= B) {
            std::vector<int> dp(n + 1, -1);
            dp[t] = 0;
            for (int j = t; j >= 1; j--) {
                if (dp[j] == -1) continue;;
                for (const auto &d: ig[j]) {
                    dp[d] = max(dp[d], dp[j] + 1);
                }
            }
            int value = -1;
            for (int g = 1; g <= t; g++) {
                if (!bl.contains(g)) value = max(value, dp[g]);
            }
            std::cout << value << "\n";
        } else {
            int value = -1;
            for (const auto &d: least[t]) {
                if (!bl.contains(d.second)) value = max(value, d.first);
            }
            std::cout << value << "\n";
        }
    }
}

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