Submission #982542

# Submission time Handle Problem Language Result Execution time Memory
982542 2024-05-14T12:03:02 Z PanosPask Sailing Race (CEOI12_race) C++14
40 / 100
534 ms 32084 KB
#include <bits/stdc++.h>
#define pb push_back
#define MOD(var, M) (((var) >= (M)) ? ((var) - M) : (var))

using namespace std;

int N, K;
vector<vector<bool>> 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
vector<vector<vector<int>>> dp;

// first[l][r][k]: True iff the first path in dp[l][r][k] is (l, r) or (r, l) respectively
vector<vector<vector<bool>>> first;

// 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
vector<vector<vector<int>>> bef;

// True if a stage can be organized from i to j
bool stage(int i, int j)
{
    return adj_list[i][j];
}

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

    adj_list.assign(N, vector<bool>(N, false));
    dp.assign(N, vector<vector<int>>(N, vector<int>(2, 0)));
    first.assign(N, vector<vector<bool>>(N, vector<bool>(2, false)));
    // bef.assign(N, vector<vector<int>>(N, vector<int>(2, 0)));

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

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

    int ans = 0;
    int starting = 0;

    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);


            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 (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]) {
                    first[l][r][0] = true;
                    dp[l][r][0] = res;
                }
            }
            if (stage(r, l)) {
                int res = 1 + dp[l][MOD(r_actual - 1, N)][0];
                if (res >= dp[l][r][1]) {
                    first[l][r][1] = true;
                    dp[l][r][1] = res;
                }
            }

            if (dp[l][r][0] > ans) {
                ans = dp[l][r][0];
                starting = l;
            }
            if (dp[l][r][1] > ans) {
                ans = dp[l][r][1];
                starting = r;
            }
        }
    }

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

    return 0;
}

Compilation message

race.cpp: In function 'int main()':
race.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%d %d", &N, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~
race.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%d", &v);
      |         ~~~~~^~~~~~~~~~
race.cpp:48:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |             scanf("%d", &v);
      |             ~~~~~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 344 KB Output isn't correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Incorrect 1 ms 604 KB Output isn't correct
5 Correct 2 ms 604 KB Output is correct
6 Incorrect 2 ms 672 KB Output isn't correct
7 Correct 3 ms 856 KB Output is correct
8 Incorrect 3 ms 1116 KB Output isn't correct
9 Correct 5 ms 1372 KB Output is correct
10 Correct 4 ms 1628 KB Output is correct
11 Correct 7 ms 1628 KB Output is correct
12 Incorrect 30 ms 5468 KB Output isn't correct
13 Incorrect 92 ms 11860 KB Output isn't correct
14 Correct 201 ms 20568 KB Output is correct
15 Incorrect 464 ms 31856 KB Output isn't correct
16 Incorrect 527 ms 31856 KB Output isn't correct
17 Incorrect 466 ms 32084 KB Output isn't correct
18 Correct 417 ms 31836 KB Output is correct
19 Incorrect 477 ms 31852 KB Output isn't correct
20 Incorrect 534 ms 31852 KB Output isn't correct