Submission #668714

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
668714	2022-12-04T16:30:29 Z	finn__	Sailing Race (CEOI12_race)	C++17	40 / 100	884 ms	3496 KB

race

#include <bits/stdc++.h>
using namespace std;

int main()
{
    size_t n, k;
    cin >> n >> k;

    vector<vector<bool>> g(n, vector<bool>(n, 0));
    for (size_t i = 0; i < n; i++)
    {
        unsigned v;
        cin >> v;
        while (v)
        {
            g[i][v - 1] = 1;
            cin >> v;
        }
    }

    vector<vector<unsigned>>
        c(n, vector<unsigned>(n, 0)),
        cc(n, vector<unsigned>(n, 0));
    unsigned max_length = 0, start = -1;

    for (size_t l = 2; l < n; l++)
    {
        for (size_t i = 0; i < n; i++)
        {
            size_t const j = (i + l) % n;

            for (size_t k = i + 1; k < i + l; k++)
            {
                if (g[i][k % n])
                    cc[i][j] =
                        max(cc[i][j], max(cc[k % n][j], c[k % n][i]) + 1);

                if (g[j][k % n])
                    c[j][i] =
                        max(c[j][i], max(cc[k % n][j], c[k % n][i]) + 1);

                if (g[j][i] && cc[i][j] + 1 > max_length)
                {
                    max_length = cc[i][j] + 1;
                    start = j + 1;
                }

                if (g[i][j] && c[j][i] + 1 > max_length)
                {
                    max_length = c[j][i] + 1;
                    start = i + 1;
                }
            }
        }
    }

    if (k == 0)
    {
        cout << max_length << '\n'
             << start << '\n';
        return 0;
    }

    vector<vector<unsigned>> longest(n, vector<unsigned>(n, 0));

    for (size_t l = 1; l < n; l++)
    {
        for (size_t i = 0; i < n; i++)
        {
            size_t const j = (i + l) % n;
            if (g[i][j])
                longest[i][j] = 1;

            for (size_t k = i + 1; k < i + l; k++)
            {
                if (longest[i][k % n] && longest[k % n][j])
                    longest[i][j] = max(longest[i][j], longest[i][k % n] + longest[k % n][j]);
            }
        }
    }
}

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Incorrect	1 ms	212 KB	Unexpected end of file - int32 expected
3	Incorrect	1 ms	304 KB	Unexpected end of file - int32 expected
4	Incorrect	1 ms	212 KB	Unexpected end of file - int32 expected
5	Correct	1 ms	212 KB	Output is correct
6	Incorrect	2 ms	340 KB	Unexpected end of file - int32 expected
7	Correct	4 ms	308 KB	Output is correct
8	Incorrect	5 ms	360 KB	Unexpected end of file - int32 expected
9	Correct	8 ms	340 KB	Output is correct
10	Correct	6 ms	340 KB	Output is correct
11	Correct	9 ms	400 KB	Output is correct
12	Incorrect	59 ms	776 KB	Unexpected end of file - int32 expected
13	Incorrect	174 ms	1312 KB	Unexpected end of file - int32 expected
14	Correct	193 ms	1740 KB	Output is correct
15	Incorrect	786 ms	3436 KB	Unexpected end of file - int32 expected
16	Incorrect	834 ms	3496 KB	Unexpected end of file - int32 expected
17	Incorrect	787 ms	3340 KB	Unexpected end of file - int32 expected
18	Correct	346 ms	2388 KB	Output is correct
19	Incorrect	876 ms	3360 KB	Unexpected end of file - int32 expected
20	Incorrect	884 ms	3488 KB	Unexpected end of file - int32 expected