Submission #1239204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239204		pvb.tunglam	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1602 ms	268248 KiB

bitaro

#include <bits/stdc++.h>
#define hash  _hash_
#define y1    _y1_
#define left  _left_
#define right _right_
#define dec   _dec_

using namespace std;
using ll = long long;
using pii = pair<int,int>;

/*----------- I alone decide my fate! ------------*/
/*  I just do what I gotta, in the heat of the summer...  */

const int MAXN = 100000 + 5;
const int B    = 320;                        // ⌈√100000⌉

int N, M, Q;
vector<int> adj[MAXN], radj[MAXN];

/* √-decomposition: lưu B ứng viên dài nhất cho mỗi đỉnh */
vector<pii> best[MAXN];                      // (len, start), giảm dần len

/* cờ đỉnh “bận” – chỉ dùng để loại ở bước lấy đáp án */
bool ban[MAXN];

/* ===== Mảng phụ trợ cho merge nhanh ===== */
int seen[MAXN], tick_seen = 0;
inline void merge_into(vector<pii>& dst,
                       const vector<pii>& src) {
    static pii buf[2 * B + 5];
    int i = 0, j = 0, p = 0, na = dst.size(), nb = src.size();
    ++tick_seen;
    while ((i < na || j < nb) && p < B) {
        pii cand;
        if (j == nb || (i < na && dst[i].first >= src[j].first + 1))
            cand = dst[i++];                         // giữ nguyên độ dài
        else {
            cand = {src[j].first + 1, src[j].second}; // +1 khi qua cạnh
            ++j;
        }
        if (seen[cand.second] != tick_seen) {
            seen[cand.second] = tick_seen;
            buf[p++] = cand;
        }
    }
    dst.assign(buf, buf + p);
}

/* ===== Phần cho truy vấn “nặng” ===== */
bool vis[MAXN];          // tập reach
int  distv[MAXN];        // độ dài tốt nhất đến T  (–1 = chưa tới)

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

    /* ---- Nhập ---- */
    cin >> N >> M >> Q;
    for (int i = 0, u, v; i < M; ++i) {
        cin >> u >> v;
        adj[u].push_back(v);
        radj[v].push_back(u);
    }

    /* ---- Khởi tạo best ---- */
    for (int u = 1; u <= N; ++u) best[u].push_back({0, u});

    /* ---- Tiền xử lý cho truy vấn nhẹ ---- */
    for (int u = 1; u <= N; ++u)
        for (int v : adj[u])
            merge_into(best[v], best[u]);

    vector<int> busy, reach;
    queue<int> que;

    /* ======================================================== */
    while (Q--) {
        int T, Y;  cin >> T >> Y;
        busy.clear();
        for (int i = 0, x; i < Y; ++i) {
            cin >> x;
            ban[x] = true;
            busy.push_back(x);
        }

        int ans = -1;

        /* ---------- Truy vấn “nhẹ” ---------- */
        if (Y < B) {
            for (const auto& p : best[T])
                if (!ban[p.second]) { ans = p.first; break; }
        }
        /* ---------- Truy vấn “nặng” ---------- */
        else {
            /* 1. BFS ngược lấy tập reach */
            reach.clear();
            que.push(T); vis[T] = true;
            while (!que.empty()) {
                int v = que.front(); que.pop();
                reach.push_back(v);
                for (int u : radj[v])
                    if (!vis[u]) { vis[u] = true; que.push(u); }
            }

            /* 2. DP topo ngược: len dài nhất tới T */
            sort(reach.begin(), reach.end(), greater<int>());
            for (int u : reach) distv[u] = -1;   // -1 = chưa tới
            distv[T] = 0;                        // gốc

            for (int u : reach) {
                if (u != T) {
                    int best_len = -1;
                    for (int v : adj[u])
                        if (vis[v] && distv[v] != -1)
                            best_len = max(best_len, distv[v] + 1);
                    distv[u] = best_len;
                }
                if (distv[u] != -1 && !ban[u])
                    ans = max(ans, distv[u]);
            }

            /* 3. Reset cờ vis cho lần sau */
            for (int u : reach) vis[u] = false;
        }

        cout << ans << '\n';

        /* ---- Gỡ cờ bận ---- */
        for (int x : busy) ban[x] = false;
    }
    return 0;
}

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