제출 #1239191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239191		pvb.tunglam	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	4 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;

/*----------- 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    = 316;                  // ≈ √(ΣY) với ΣY ≤100k → 316

int N, M, Q;
vector<int> adj[MAXN], radj[MAXN];
vector<pair<int,int>> best[MAXN];       // (len, start), giảm dần len
bool ban[MAXN];                         // cờ đỉnh bận

// cho merge: đánh dấu nhanh các start đã thêm
int seen[MAXN], merge_timer = 0;

/// gộp src → dst, cộng len+1, giữ tối đa B, loại trùng start O(1)
void merge_into(vector<pair<int,int>> &dst,
                const vector<pair<int,int>> &src)
{
    static pair<int,int> buf[2 * B];
    int na = dst.size(), nb = src.size();
    int i = 0, j = 0, p = 0;
    ++merge_timer;
    while ((i < na || j < nb) && p < B) {
        pair<int,int> 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] != merge_timer) {
            seen[s] = merge_timer;
            buf[p++] = cand;
        }
    }
    dst.assign(buf, buf + p);
}

// cho truy vấn nặng
bool vis[MAXN];
int distv[MAXN];

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

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

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

    // 2) Tiền xử lý (N+M)*B
    for (int u = 1; u <= N; ++u) {
        for (int v: adj[u]) {
            merge_into(best[v], best[u]);
        }
    }

    vector<int> busy_list, reach;
    queue<int> bfsq;

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

        int answer = -1;
        if (Y < B) {
            // --- truy vấn nhẹ O(B) ---
            for (auto &p: best[T]) {
                if (!ban[p.second]) {
                    answer = p.first;
                    break;
                }
            }
        } else {
            // --- truy vấn nặng: BFS ngược + DP topo ngược ---
            reach.clear();
            bfsq.push(T);
            vis[T] = true;
            while (!bfsq.empty()) {
                int v = bfsq.front(); bfsq.pop();
                reach.push_back(v);
                for (int u: radj[v]) {
                    if (!vis[u]) {
                        vis[u] = true;
                        bfsq.push(u);
                    }
                }
            }
            // xử lý DP theo thứ tự giảm u (bởi S<E)
            sort(reach.begin(), reach.end(), greater<int>());
            answer = -1;
            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)
                    answer = max(answer, distv[u]);
            }
            // reset vis và distv chỉ với reach
            for (int u: reach) {
                vis[u] = false;
                // distv[u] sẽ được ghi đè ở lần tiếp theo khi cần
            }
        }

        cout << answer << "\n";
        // clear ban flags
        for (int x: busy_list) ban[x] = false;
    }

    return 0;
}

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