제출 #1239198

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239198		pvb.tunglam	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	7 ms	7752 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: bảng ứng viên --------- */
vector<pii> best[MAXN];                   // (len, start), giảm dần len

/* --------- trạng thái truy vấn --------- */
bool ban[MAXN];                           // đỉnh bận

/* --------- bộ nhớ tạm cho merge --------- */
int seen[MAXN], tick_seen;

/* gộp best[src] (cộng +1) vào best[dst] và giữ tối đa B */
void merge_into(vector<pii>& dst, const vector<pii>& src) {
    static pii buf[2 * B + 5];
    int i = 0, j = 0, p = 0;
    int 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++];
        else {
            cand = {src[j].first + 1, src[j].second};
            ++j;
        }
        int s = cand.second;
        if (seen[s] != tick_seen) {
            seen[s] = tick_seen;
            buf[p++] = cand;
        }
    }
    dst.assign(buf, buf + p);
}

/* --------- truy vấn nặng --------- */
bool vis[MAXN];           // BFS ngược
int  distv[MAXN];         // dp cục bộ

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

    /* ---- đọc dữ liệu ---- */
    if(!(cin >> N >> M >> Q)) return 0;
    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 {
            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); }
            }

            /* topo ngược: chỉ số giảm dần vì S<E */
            sort(reach.begin(), reach.end(), greater<int>());

            ans = 0;
            for (int u : reach) {
                int best_len = ban[u] ? INT_MIN/2 : 0;
                for (int v : adj[u])
                    if (vis[v])
                        best_len = max(best_len, distv[v] + 1);
                distv[u] = best_len;
                if (!ban[u] && distv[u] >= 0)
                    ans = max(ans, distv[u]);
            }

            /* reset cờ 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: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86