Submission #1239187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239187		pvb.tunglam	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2093 ms	13284 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    = 320;                  // v(SYj) ˜ 320

int N, M, Q;
vector<int> adj[MAXN], radj[MAXN];
vector<pair<int,int>> best[MAXN];       // (len, start), gi?m d?n theo len
bool ban[MAXN];                         // d?nh b?n

int dp[MAXN];                           // dùng cho truy v?n n?ng
bool vis_dp[MAXN];                      // c? “dã tính dp[u]”

/// G?p best[src] (dã s?p gi?m d?n) vào best[dst], c?ng len+1
void merge_into(vector<pair<int,int>> &dst,
                const vector<pair<int,int>> &src)
{
    static pair<int,int> buf[2 * B];
    int i = 0, j = 0, p = 0;
    int na = dst.size(), nb = src.size();
    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;
        }
        // lo?i trùng start
        bool dup = false;
        for (int k = 0; k < p; ++k) {
            if (buf[k].second == cand.second) {
                dup = true;
                break;
            }
        }
        if (!dup) buf[p++] = cand;
    }
    dst.assign(buf, buf + p);
}

/// Tính dp[u] = du?ng di dài nh?t k?t thúc ? u, b? qua các u b? ban
int calc(int u) {
    if (vis_dp[u]) return dp[u];
    vis_dp[u] = true;
    dp[u] = ban[u] ? INT_MIN/2 : 0;
    for (int v: radj[u]) {
        int t = calc(v);
        dp[u] = max(dp[u], t + 1);
    }
    return dp[u];
}

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] v?i (len=0, start=u)
    for (int u = 1; u <= N; ++u) {
        best[u].push_back({0, u});
    }

    // 2) Ti?n x? lý cho truy v?n “nh?”
    //    Duy?t topo (1..N) vì d? th? DAG (S < E)
    for (int u = 1; u <= N; ++u) {
        for (int v: adj[u]) {
            merge_into(best[v], best[u]);
        }
    }

    vector<int> busy_list;
    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? ---
            for (auto &p: best[T]) {
                if (!ban[p.second]) {
                    answer = p.first;
                    break;
                }
            }
        } else {
            // --- truy v?n n?ng ---
            // reset c? vis_dp[]
            fill(vis_dp+1, vis_dp+N+1, false);
            int res = calc(T);
            answer = (res < 0 ? -1 : res);
        }

        cout << answer << "\n";

        // xoá dánh d?u ban[]
        for (int x: busy_list) {
            ban[x] = false;
        }
    }
    return 0;
}

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