Submission #983218

#	Time	Username	Problem	Language	Result	Execution time	Memory
983218		PanosPask	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1164 ms	262504 KiB

bitaro

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

typedef pair<int, int> pi;

int CUTOFF;
int N, M, Q;
vector<vector<int>> adj_list;
vector<vector<pi>> dist;

vector<bool> banned;

// Only for local use in merge
// Make sure to reset after
vector<bool> used;

void push(vector<pi>& v, pi p, int m)
{
    if (used[p.second]) {
        return;
    }

    v.pb({p.first + m, p.second});
    used[p.second] = true;
}

// a is the list we want to update
// b is from a neighbour,therefore everything +1
void merge(vector<pi>& a, vector<pi>& b)
{
    vector<pi> c;

    int a_p = 0, b_p = 0;
    while (a_p < a.size() && b_p < b.size() && c.size() < CUTOFF) {
        if (a[a_p].first >= b[b_p].first + 1) {
            push(c, a[a_p], 0);
            a_p++;
        }
        else {
            push(c, b[b_p], 1);
            b_p++;
        }
    }
    while (c.size() < CUTOFF && a_p < a.size()) {
        push(c, a[a_p], 0);
        a_p++;
    }
    while (c.size() < CUTOFF && b_p < b.size()) {
        push(c, b[b_p], 1);
        b_p++;
    }

    a = c;
    for (auto& [v, i] : a) {
        used[i] = false;
    }
}

int calc_all(int t)
{
    vector<int> dp;
    dp.assign(N, -1);

    for (int u = 0; u <= t; u++) {
        if (banned[u] && dp[u] == -1) {
            continue;
        }
        dp[u] = max(dp[u], 0);

        for (auto v : adj_list[u]) {
            dp[v] = max(dp[v], dp[u] + 1);
        }
    }

    return dp[t];
}

int choose_from_calced(int t)
{
    for (auto [s, v] : dist[t]) {
        if (!banned[v]) {
            return s;
        }
    }

    return -1;
}

int main(void)
{
    scanf("%d %d %d", &N, &M, &Q);

    CUTOFF = sqrt(N);

    adj_list.resize(N);
    banned.assign(N, false);
    dist.resize(N);
    used.assign(N, false);

    for (int i = 0; i < M; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        u--; v--;

        adj_list[u].pb(v);
    }

    for (int i = 0; i < N; i++) {
        if (dist[i].size() < CUTOFF) {
            dist[i].pb({0, i});
        }

        for (auto neigh : adj_list[i]) {
            merge(dist[neigh], dist[i]);
        }
    }

    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]--;
            banned[c[i]] = true;
        }

        if (Y >= CUTOFF) {
            printf("%d\n", calc_all(T));
        }
        else {
            printf("%d\n", choose_from_calced(T));
        }

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

    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void merge(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
bitaro.cpp:36:16: 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 |     while (a_p < a.size() && b_p < b.size() && c.size() < CUTOFF) {
      |            ~~~~^~~~~~~~~~
bitaro.cpp:36:34: 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 |     while (a_p < a.size() && b_p < b.size() && c.size() < CUTOFF) {
      |                              ~~~~^~~~~~~~~~
bitaro.cpp:36:57: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |     while (a_p < a.size() && b_p < b.size() && c.size() < CUTOFF) {
      |                                                ~~~~~~~~~^~~~~~~~
bitaro.cpp:46:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |     while (c.size() < CUTOFF && a_p < a.size()) {
      |            ~~~~~~~~~^~~~~~~~
bitaro.cpp:46:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     while (c.size() < CUTOFF && a_p < a.size()) {
      |                                 ~~~~^~~~~~~~~~
bitaro.cpp:50:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |     while (c.size() < CUTOFF && b_p < b.size()) {
      |            ~~~~~~~~~^~~~~~~~
bitaro.cpp:50:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     while (c.size() < CUTOFF && b_p < b.size()) {
      |                                 ~~~~^~~~~~~~~~
bitaro.cpp:56:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     for (auto& [v, i] : a) {
      |                ^
bitaro.cpp: In function 'int choose_from_calced(int)':
bitaro.cpp:82:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |     for (auto [s, v] : dist[t]) {
      |               ^
bitaro.cpp: In function 'int main()':
bitaro.cpp:111:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  111 |         if (dist[i].size() < CUTOFF) {
      |             ~~~~~~~~~~~~~~~^~~~~~~~
bitaro.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |     scanf("%d %d %d", &N, &M, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         scanf("%d %d", &T, &Y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:127:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |             scanf("%d", &c[i]);
      |             ~~~~~^~~~~~~~~~~~~

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