Submission #982536

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
982536	2024-05-14T11:32:38 Z	PanosPask	Sailing Race (CEOI12_race)	C++14	40 / 100	3000 ms	14516 KB

race

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

using namespace std;

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

// True if a stage can be organized from i to j
bool stage(int i, int j)
{
    int pos = lower_bound(adj_list[i].begin(), adj_list[i].end(), j) - adj_list[i].begin();
    if (pos < adj_list[i].size() && adj_list[i][pos] == j) {
        return true;
    }

    return false;
}

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

    adj_list.resize(N);
    dp.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].pb(v);
            scanf("%d", &v);
        }

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

    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 = r_actual % N;

            for (int i_actual = l + 1; i_actual < r_actual; i_actual++) {
                int i = 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)) {
                dp[l][r][0] = max(dp[l][r][0], 1 + dp[(l + 1) % N][r][1]);
            }
            if (stage(r, l)) {
                dp[l][r][1] = max(dp[l][r][1], 1 + dp[l][(r_actual - 1) % N][0]);
            }

            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 'bool stage(int, int)':
race.cpp:21:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     if (pos < adj_list[i].size() && adj_list[i][pos] == j) {
      |         ~~~~^~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'int main()':
race.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%d %d", &N, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~
race.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d", &v);
      |         ~~~~~^~~~~~~~~~
race.cpp:42:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |             scanf("%d", &v);
      |             ~~~~~^~~~~~~~~~

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Incorrect	1 ms	348 KB	Output isn't correct
3	Incorrect	1 ms	348 KB	Output isn't correct
4	Incorrect	2 ms	348 KB	Output isn't correct
5	Correct	4 ms	348 KB	Output is correct
6	Incorrect	6 ms	860 KB	Output isn't correct
7	Correct	11 ms	604 KB	Output is correct
8	Incorrect	11 ms	612 KB	Output isn't correct
9	Correct	22 ms	868 KB	Output is correct
10	Correct	14 ms	860 KB	Output is correct
11	Correct	30 ms	860 KB	Output is correct
12	Incorrect	161 ms	2680 KB	Output isn't correct
13	Incorrect	434 ms	5440 KB	Output isn't correct
14	Correct	934 ms	9312 KB	Output is correct
15	Incorrect	2705 ms	14396 KB	Output isn't correct
16	Incorrect	2985 ms	14516 KB	Output isn't correct
17	Incorrect	2621 ms	14400 KB	Output isn't correct
18	Correct	1575 ms	14268 KB	Output is correct
19	Execution timed out	3065 ms	14428 KB	Time limit exceeded
20	Execution timed out	3012 ms	14432 KB	Time limit exceeded