Submission #644075

#	Time	Username	Problem	Language	Result	Execution time	Memory
644075		valerikk	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1999 ms	151100 KiB

bitaro

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100001;

int n, m, q;
vector<int> g[MAXN];

bool bad[MAXN];
int dp[MAXN];
vector<pair<int, int>> best[MAXN];
bool used[MAXN];

int main() {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 0; i < m; ++i) {
        int s, e;
        scanf("%d%d", &s, &e);
        --s, --e;
        g[s].push_back(e);
    }

    for (int v = 0; v < n; ++v) {
        best[v].push_back({0, v});
    }
    for (int v = 0; v < n; ++v) {
        sort(best[v].rbegin(), best[v].rend());
        for (auto p : best[v]) {
            used[p.second] = false;
        }

        vector<pair<int, int>> tmp;
        tmp.reserve(120);
        for (auto p : best[v]) {
            if (tmp.size() == 120) 
                break;

            if (!used[p.second]) {
                tmp.push_back(p);
                used[p.second] = true;
            }
        }

        swap(best[v], tmp);

        for (int u : g[v]) {
            for (auto p : best[v]) {
                best[u].push_back({p.first + 1, p.second});
            }
        }
    }   

    while (q--) {
        int t, y;
        scanf("%d%d", &t, &y);
        --t;

        vector<int> c(y);
        for (int i = 0; i < y; ++i) {
            scanf("%d", &c[i]);
            --c[i];
        }

        for (int i = 0; i < y; ++i) {
            bad[c[i]] = true;
        }

        if (y >= 120) {
            for (int v = 0; v < n; ++v) {
                dp[v] = bad[v] ? -1 : 0;
            }
            
            for (int v = 0; v < n; ++v) {
                if (dp[v] == -1)
                    continue;
                for (int u : g[v]) {
                    dp[u] = max(dp[u], dp[v] + 1);
                }
            }
            
            printf("%d\n", dp[t]);
        } else {
            int ans = -1;
            for (auto p : best[t]) {
                if (!bad[p.second]) 
                    ans = max(ans, p.first);
            }

            printf("%d\n", ans);
        }

        for (int i = 0; i < y; ++i) {
            bad[c[i]] = false;
        }
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%d%d%d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf("%d%d", &s, &e);
      |         ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf("%d%d", &t, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:64:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |             scanf("%d", &c[i]);
      |             ~~~~~^~~~~~~~~~~~~

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