Submission #668712

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
668712	2022-12-04T16:23:59 Z	finn__	Sailing Race (CEOI12_race)	C++17	10 / 100	599 ms	6728 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[i][j] && max(c[i][j], cc[i][j]) + 1 > max_length)
                {
                    max_length = max(c[i][j], cc[i][j]) + 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] && longest[k][j])
                    longest[i][j] = max(longest[i][j], longest[i][k] + longest[k][j]);
            }
        }
    }
}

Subtask #1

10.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	212 KB	Output isn't correct
2	Runtime error	1 ms	340 KB	Execution killed with signal 11
3	Runtime error	1 ms	340 KB	Execution killed with signal 11
4	Runtime error	1 ms	468 KB	Execution killed with signal 11
5	Incorrect	2 ms	304 KB	Output isn't correct
6	Runtime error	2 ms	468 KB	Execution killed with signal 11
7	Incorrect	3 ms	340 KB	Output isn't correct
8	Runtime error	3 ms	596 KB	Execution killed with signal 11
9	Correct	6 ms	308 KB	Output is correct
10	Correct	7 ms	340 KB	Output is correct
11	Incorrect	9 ms	312 KB	Output isn't correct
12	Runtime error	38 ms	1356 KB	Execution killed with signal 11
13	Runtime error	93 ms	2588 KB	Execution killed with signal 11
14	Incorrect	199 ms	1636 KB	Output isn't correct
15	Runtime error	476 ms	6664 KB	Execution killed with signal 11
16	Runtime error	518 ms	6704 KB	Execution killed with signal 11
17	Runtime error	474 ms	6664 KB	Execution killed with signal 11
18	Incorrect	355 ms	2368 KB	Output isn't correct
19	Runtime error	564 ms	6724 KB	Execution killed with signal 11
20	Runtime error	599 ms	6728 KB	Execution killed with signal 11