Submission #668718

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
668718	2022-12-04T16:55:23 Z	finn__	Sailing Race (CEOI12_race)	C++17	40 / 100	3000 ms	3240 KB

race

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

size_t n;
vector<vector<bool>> g;
vector<vector<unsigned>> c, cc, longest;
unsigned max_length = 0, start = -1;

void longest_route()
{
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = i + 1; j < i + n; j++)
        {
            if (longest[i][j % n])
            {
                unsigned a = -1;
                for (size_t k = j + 1; (k % n) > (j % n) || (k % n) < i; k++)
                {
                    if (g[k % n][i])
                    {
                        a = k % n;
                        break;
                    }
                }

                if (a == UINT_MAX)
                    continue;

                for (size_t k = a + 1; (k % n) > a || (k % n) < i; k++)
                {
                    if (g[j % n][k % n])
                    {
                        unsigned l = 2 + longest[i][j % n] + max(cc[k % n][i], c[k % n][a]);
                        if (l > max_length)
                        {
                            max_length = l;
                            start = a + 1;
                        }
                    }
                }
            }
        }
    }
}

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

    g = vector<vector<bool>>(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;
        }
    }

    c = vector<vector<unsigned>>(n, vector<unsigned>(n, 0));
    cc = vector<vector<unsigned>>(n, vector<unsigned>(n, 0));

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

    longest = vector<vector<unsigned>>(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]);
            }
        }
    }

    longest_route();
    vector<bool> &y = g.back();
    for (size_t i = 0; i < n; i++)
        swap(y, g[i]);
    longest_route();

    cout << max_length << '\n'
         << start << '\n';
}

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Execution timed out	3091 ms	212 KB	Time limit exceeded
3	Execution timed out	3052 ms	212 KB	Time limit exceeded
4	Execution timed out	3072 ms	212 KB	Time limit exceeded
5	Correct	1 ms	212 KB	Output is correct
6	Execution timed out	3073 ms	328 KB	Time limit exceeded
7	Correct	4 ms	340 KB	Output is correct
8	Execution timed out	3077 ms	340 KB	Time limit exceeded
9	Correct	7 ms	372 KB	Output is correct
10	Correct	6 ms	388 KB	Output is correct
11	Correct	9 ms	384 KB	Output is correct
12	Execution timed out	3069 ms	764 KB	Time limit exceeded
13	Execution timed out	3057 ms	1356 KB	Time limit exceeded
14	Correct	198 ms	1604 KB	Output is correct
15	Execution timed out	3076 ms	3228 KB	Time limit exceeded
16	Execution timed out	3083 ms	3240 KB	Time limit exceeded
17	Execution timed out	3069 ms	3240 KB	Time limit exceeded
18	Correct	359 ms	2260 KB	Output is correct
19	Execution timed out	3079 ms	3228 KB	Time limit exceeded
20	Execution timed out	3079 ms	3232 KB	Time limit exceeded