Submission #1324055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1324055		sh_qaxxorov_571	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	771 ms	412120 KiB

bitaro

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100005;
const int B = 320; // Kvadrat ildiz chegarasi

vector<int> adj[MAXN];
vector<pair<int, int>> best[MAXN]; // {masofa, shahar}
int dist[MAXN], busy[MAXN];

// Ikkita saralangan ro'yxatni birlashtirib, eng yaxshi B tasini saqlash
vector<pair<int, int>> merge(const vector<pair<int, int>>& v1, const vector<pair<int, int>>& v2) {
    vector<pair<int, int>> res;
    int i = 0, j = 0;
    static bool used[MAXN];
    
    while (res.size() < B && (i < v1.size() || j < v2.size())) {
        pair<int, int> next;
        if (i < v1.size() && (j == v2.size() || v1[i].first > v2[j].first + 1)) {
            next = v1[i++];
        } else {
            next = {v2[j].first + 1, v2[j].second};
            j++;
        }
        if (!used[next.second]) {
            used[next.second] = true;
            res.push_back(next);
        }
    }
    for (auto& p : res) used[p.second] = false;
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, Q;
    cin >> N >> M >> Q;

    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        adj[v].push_back(u); // Teskari yo'nalishda saqlaymiz
    }

    // 1. Oldindan DP orqali har bir shahar uchun eng yaxshi B ta masofani hisoblash
    for (int i = 1; i <= N; i++) {
        best[i].push_back({0, i});
        for (int prev : adj[i]) {
            best[i] = merge(best[i], best[prev]);
        }
    }

    // 2. So'rovlarni qayta ishlash
    while (Q--) {
        int T, Y;
        cin >> T >> Y;
        vector<int> C(Y);
        for (int i = 0; i < Y; i++) {
            cin >> C[i];
            busy[C[i]] = 1;
        }

        if (Y < B) {
            // Kam bandlar: Tayyor ro'yxatdan qidiramiz
            int ans = -1;
            for (auto& p : best[T]) {
                if (!busy[p.second]) {
                    ans = p.first;
                    break;
                }
            }
            cout << ans << "\n";
        } else {
            // Ko'p bandlar: DP orqali hisoblaymiz
            vector<int> dp(T + 1, -1);
            dp[T] = 0;
            int ans = -1;
            for (int i = T; i >= 1; i--) {
                if (dp[i] == -1) continue;
                if (!busy[i]) ans = max(ans, dp[i]);
                for (int next : adj[i]) {
                    dp[next] = max(dp[next], dp[i] + 1);
                }
            }
            cout << ans << "\n";
        }

        // Bandlarni tozalash
        for (int x : C) busy[x] = 0;
    }

    return 0;
}

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