Submission #554398

#	Time	Username	Problem	Language	Result	Execution time	Memory
554398		Alexandruabcde	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1509 ms	420024 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> PII;
constexpr int NMAX = 1e5 + 5;
constexpr int BUCKET = 300;

int N, M, Q;
vector <int> To[NMAX];
vector <int> From[NMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M >> Q;

    for (int i = 1; i <= M; ++ i ) {
        int x, y;
        cin >> x >> y;

        To[x].push_back(y);
        From[y].push_back(x);
    }
}
///           length who
vector <pair <int, int> > Best[NMAX];
bool viz[NMAX];

vector <PII> MergeSort (int who, vector <PII> A, vector <PII> Before) {
    int i = 0, j = 0;
    vector <PII> ans;

    while (ans.size() < BUCKET && (i < A.size() || j < Before.size())) {
        if (i == A.size()) {
            if (!viz[Before[j].second]) {
                ans.push_back({Before[j].first + 1, Before[j].second});
            }
            viz[Before[j].second] = true;
            ++ j;
        }
        else if (j == Before.size()) {
            if (!viz[A[i].second]) {
                ans.push_back(A[i]);
            }
            viz[A[i].second] = true;
            ++ i;
        }
        else {
            if (A[i].first >= Before[j].first + 1) {
                if (!viz[A[i].second]) {
                    ans.push_back(A[i]);
                }
                viz[A[i].second] = true;
                ++ i;
            }
            else {
                if (!viz[Before[j].second]) {
                    ans.push_back({Before[j].first+1, Before[j].second});
                }
                viz[Before[j].second] = true;
                ++ j;
            }
        }
    }

    for (auto it : ans)
        viz[it.second] = false;

    return ans;
}

void Precompute () {
    for (int i = 1; i <= N; ++ i ) {
        for (auto it : From[i]) {
            Best[i] = MergeSort(i, Best[i], Best[it]);
        }

        if (Best[i].size() < BUCKET) {
            Best[i].push_back({0, i});
        }
    }
}

bool busy[NMAX];
int dp[NMAX];

void Solve () {
    for (; Q; -- Q ) {
        int X, Y;
        cin >> X >> Y;

        vector <int> whom;
        for (int i = 1; i <= Y; ++ i ) {
            int a;
            cin >> a;
            whom.push_back(a);
            busy[a] = 1;
        }

        int ans = -1;

        if (Y < BUCKET) {
            for (auto it : Best[X]) {
                if (busy[it.second]) continue;

                ans = max(ans, it.first);
            }
        }
        else {
            for (int i = 1; i <= N; ++ i )
                dp[i] = -1;
            dp[X] = 0;

            for (int i = X; i >= 1; -- i ) {
                for (auto it : To[i]) {
                    if (dp[it] == -1) continue;

                    dp[i] = max(dp[i], dp[it] + 1);
                }

                if (busy[i]) continue;
                ans = max(ans, dp[i]);
            }
        }

        cout << ans << '\n';

        for (auto it : whom)
            busy[it] = 0;
    }
}

int main () {
    Read();
    Precompute();
    Solve();

    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'std::vector<std::pair<int, int> > MergeSort(int, std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
bitaro.cpp:35:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     while (ans.size() < BUCKET && (i < A.size() || j < Before.size())) {
      |                                    ~~^~~~~~~~~~
bitaro.cpp:35:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     while (ans.size() < BUCKET && (i < A.size() || j < Before.size())) {
      |                                                    ~~^~~~~~~~~~~~~~~
bitaro.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         if (i == A.size()) {
      |             ~~^~~~~~~~~~~
bitaro.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         else if (j == Before.size()) {
      |                  ~~^~~~~~~~~~~~~~~~

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