제출 #1288654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288654		c4l	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1950 ms	199796 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
const int NEG_INF = -1000000000;

// TUNABLE: kích thước bucket (trade-off tiền xử lý <-> trả lời truy vấn nhỏ)
// Bạn có thể thử 180..300; mình đặt 200 để an toàn về bộ nhớ.
const int B = 200;

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

    int N, M, Q;
    if(!(cin >> N >> M >> Q)) return 0;

    vector<vector<int>> rev_adj(N+1); // rev_adj[v] chứa các u sao cho u -> v (u < v)
    vector<vector<int>> out_adj(N+1); // out_adj[u] chứa các v sao cho u -> v (v > u)
    for(int i=0;i<M;i++){
        int s,e; cin >> s >> e;
        // theo đề: kênh chạy từ cao xuống thấp, chỉ số nhỏ -> lớn
        // tổng quát: có cung s->e
        out_adj[s].push_back(e);
        rev_adj[e].push_back(s);
    }

    // dp[v]: tối đa giữ B cặp (len, src) nghĩa là "từ src -> v có đường dài = len"
    vector<vector<pii>> dp(N+1);
    vector<int> seen(N+1, 0);
    int seenTime = 1;

    // Xây dp tăng dần v = 1..N
    for(int v = 1; v <= N; ++v){
        // thu thập các ứng viên: (0, v) + từ mỗi w trước v (w->v) lấy dp[w] + 1
        vector<pii> cand;
        cand.reserve(1 + (int)rev_adj[v].size() * B);
        cand.emplace_back(0, v);
        for(int w : rev_adj[v]){
            for(auto &p : dp[w]){
                cand.emplace_back(p.first + 1, p.second);
            }
        }
        // sắp xếp giảm dần theo length (nếu bằng thì theo node nhỏ)
        sort(cand.begin(), cand.end(), [](const pii &a, const pii &b){
            if(a.first != b.first) return a.first > b.first;
            return a.second < b.second;
        });
        // chọn top B với đỉnh nguồn duy nhất
        vector<pii> out;
        out.reserve(min((int)cand.size(), B));
        ++seenTime;
        for(auto &p : cand){
            if((int)out.size() >= B) break;
            int node = p.second;
            if(seen[node] == seenTime) continue;
            seen[node] = seenTime;
            out.push_back(p);
        }
        dp[v].swap(out);
    }

    vector<int> forbidden(N+1, 0);
    int curMark = 1;
    vector<int> best(N+2, NEG_INF);

    // xử lý Q truy vấn
    for(int qi = 0; qi < Q; ++qi){
        int T, Y;
        cin >> T >> Y;
        vector<int> forb(Y);
        for(int i=0;i<Y;i++) cin >> forb[i];

        if(Y < B){
            // trường hợp nhỏ: đánh dấu các forb và quét dp[T]
            ++curMark;
            for(int x : forb) if(1 <= x && x <= N) forbidden[x] = curMark;
            int ans = -1;
            for(auto &p : dp[T]){
                int len = p.first;
                int src = p.second;
                if(forbidden[src] == curMark) continue; // nguồn bị cấm
                ans = len;
                break;
            }
            cout << ans << '\n';
        } else {
            // trường hợp lớn: chạy DP từ T trên prefix 1..T (không loại nút trung gian)
            // best[i] = max length from i -> T (or NEG_INF nếu ko tới được)
            for(int i = 1; i <= T; ++i) best[i] = NEG_INF;
            best[T] = 0;
            // duyệt i từ T-1..1 (cũng có thể từ T downto 1), vì các cạnh i->v có v>i
            for(int i = T; i >= 1; --i){
                // nếu i == T thì best[T] đã = 0; nhưng vẫn duyệt ra
                for(int v : out_adj[i]){
                    if(v > T) continue; // ngoài prefix T
                    if(best[v] != NEG_INF){
                        best[i] = max(best[i], best[v] + 1);
                    }
                }
            }
            // đánh dấu forbidden (chỉ dùng để loại nguồn khi lấy max)
            ++curMark;
            for(int x : forb) if(1 <= x && x <= N) forbidden[x] = curMark;
            int ans = -1;
            for(int i = 1; i <= T; ++i){
                if(best[i] == NEG_INF) continue;
                if(forbidden[i] == curMark) continue; // nguồn bị cấm
                ans = max(ans, best[i]);
            }
            cout << ans << '\n';
        }
    }

    return 0;
}

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