Submission #982591

# Submission time Handle Problem Language Result Execution time Memory
982591 2024-05-14T13:03:33 Z PanosPask Sailing Race (CEOI12_race) C++14
45 / 100
1703 ms 5092 KB
/*This problem needs arrays instad of vectors due to
extremely tight ML and TL*/

#include <bits/stdc++.h>
#define pb push_back
#define MOD(var, M) (((var) >= (M)) ? ((var) - M) : (var))

using namespace std;

const int MAXN = 500;
const int INF = 1e9;

int N, K;
bool stage[MAXN][MAXN];

vector<vector<int>> adj_list;

// dp[l][r][k]:  Maximum number of stages if enclosed by l, r
// and being in the stages such that l < s < r'
// Where r' = l > r ? r = r + N : r

// k == 0: Starting in l
// k == 1: Starting in r
int dp[MAXN][MAXN][2];

// Before the intersection with the first stage
// You can only choose one way to follow
// Either from l to r or from r to l
int bef[MAXN][MAXN][2];

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

    adj_list.resize(N);

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

        while (v != 0) {
            v--;
            stage[i][v] = true;
            adj_list[i].pb(v);
            adj_list[i].pb(v + N);
            scanf("%d", &v);
        }

        sort(adj_list[i].begin(), adj_list[i].end());
    }

    for (int len = 1; len <= N; len++) {
        for (int l = 0; l < N; l++) {
            int r_actual = l + len - 1;
            int r = MOD(r_actual, N);

            bef[l][r][0] = bef[l][r][1] = -INF;

            for (int i_actual = l + 1; i_actual < r_actual; i_actual++) {
                int i = MOD(i_actual, N);

                dp[l][r][0] = max(dp[l][r][0], dp[l][i][0]);
                dp[l][r][1] = max(dp[l][r][1], dp[i][r][1]);

                if (bef[l][i][0] != -INF && bef[i][r][0] != -INF) {
                    bef[l][r][0] = max(bef[l][r][0], bef[l][i][0] + bef[i][r][0]);
                }
                if (bef[l][i][1] != -INF && bef[i][r][1] != -INF) {
                    bef[l][r][1] = max(bef[l][r][1], bef[l][i][1] + bef[i][r][1]);
                }

                if (stage[l][i]) {
                    dp[l][r][0] = max(dp[l][r][0], 1 + dp[i][r][0]);
                }
                if (stage[r][i]) {
                    dp[l][r][1] = max(dp[l][r][1], 1 + dp[l][i][1]);
                }
            }

            if (stage[l][r]) {
                int res = 1 + dp[MOD(l + 1, N)][r][1];
                if (res >= dp[l][r][0]) {
                    dp[l][r][0] = res;
                }

                bef[l][r][0] = max(bef[l][r][0], 1);
            }
            if (stage[r][l]) {
                int res = 1 + dp[l][MOD(r_actual - 1, N)][0];
                if (res >= dp[l][r][1]) {
                    dp[l][r][1] = res;
                }

                bef[l][r][1] = max(bef[l][r][1], 1);
            }
        }
    }

    int ans = 0;
    int starting = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (dp[i][j][0] > ans) {
                ans = dp[i][j][0];
                starting = i;
            }
            if (dp[i][j][1] > ans) {
                ans = dp[i][j][1];
                starting = j;
            }
        }
    }
    if (K == 0) {
        printf("%d\n%d\n", ans, starting + 1);
        return 0;
    }

    // Unite bef(before intersection) with dp(after intersection)
    for (int len = 0; len <= N; len++) {
        for (int l = 0; l < N; l++) {
            int r_actual = l + len - 1;
            int r = MOD(r_actual, N);

            bool g1 = stage[l][r];
            bool g2 = stage[r][l];

            for (int i_actual = l + 1; i_actual < r_actual; i_actual++) {
                int i = MOD(i_actual, N);

                int res = -INF;
                int s = -1;
                if (g1) {
                    res = bef[l][i][0];
                    s = l;
                }
                if (g2 && res < bef[i][r][1]) {
                    res = bef[i][r][1];
                    s = r;
                }
                res++;

                if (res < 0) {
                    continue;
                }

                int j1 = upper_bound(adj_list[i].begin(), adj_list[i].end(), r_actual) - adj_list[i].begin();
                int j2 = lower_bound(adj_list[i].begin(), adj_list[i].end(), N + l) - adj_list[i].begin() - 1;

                int v = 0;
                if (j1 < adj_list[i].size()) {
                    int n1 = adj_list[i][j1];
                    if (n1 < l + N) {
                        v = max(v, 1 + dp[MOD(n1, N)][MOD(l - 1 + N, N)][0]);
                    }
                }
                if (j2 >= 0) {
                    int n2 = adj_list[i][j2];
                    if (n2 > r_actual) {
                        v = max(v, 1 + dp[MOD(r + 1, N)][MOD(n2, N)][1]);
                    }
                }

                if (ans < v + res) {
                    ans = v + res;
                    starting = s;
                }
            }
        }
    }

    printf("%d\n%d\n", ans, starting + 1);

    return 0;
}

Compilation message

race.cpp: In function 'int main()':
race.cpp:150:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |                 if (j1 < adj_list[i].size()) {
      |                     ~~~^~~~~~~~~~~~~~~~~~~~
race.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d %d", &N, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~
race.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         scanf("%d", &v);
      |         ~~~~~^~~~~~~~~~
race.cpp:46:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |             scanf("%d", &v);
      |             ~~~~~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Incorrect 1 ms 600 KB Output isn't correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 4 ms 2648 KB Output is correct
7 Correct 3 ms 2652 KB Output is correct
8 Incorrect 6 ms 2652 KB Output isn't correct
9 Correct 5 ms 2652 KB Output is correct
10 Correct 5 ms 2908 KB Output is correct
11 Correct 7 ms 2652 KB Output is correct
12 Incorrect 93 ms 3164 KB Output isn't correct
13 Incorrect 214 ms 3676 KB Output isn't correct
14 Correct 276 ms 4252 KB Output is correct
15 Incorrect 1171 ms 4872 KB Output isn't correct
16 Incorrect 1422 ms 5060 KB Output isn't correct
17 Incorrect 1201 ms 4700 KB Output isn't correct
18 Correct 546 ms 4700 KB Output is correct
19 Incorrect 1703 ms 5092 KB Output isn't correct
20 Incorrect 1648 ms 5084 KB Output isn't correct