Submission #668717

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
668717	2022-12-04T16:51:52 Z	finn__	Sailing Race (CEOI12_race)	C++17	40 / 100	3000 ms	3232 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 % n) + 1; k > (j % n) || (k % n) < i; k++)
                {
                    if (g[j % n][i])
                    {
                        a = k % n;
                        break;
                    }
                }

                if (a == UINT_MAX)
                    continue;

                for (size_t k = a + 1; k > a || (k % n) < i; k++)
                {
                    if (g[j % n][j % 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	0 ms	212 KB	Output is correct
2	Execution timed out	3075 ms	212 KB	Time limit exceeded
3	Execution timed out	3076 ms	212 KB	Time limit exceeded
4	Execution timed out	3091 ms	212 KB	Time limit exceeded
5	Correct	2 ms	212 KB	Output is correct
6	Execution timed out	3076 ms	340 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	340 KB	Output is correct
10	Correct	6 ms	308 KB	Output is correct
11	Correct	10 ms	388 KB	Output is correct
12	Execution timed out	3066 ms	764 KB	Time limit exceeded
13	Execution timed out	3077 ms	1284 KB	Time limit exceeded
14	Correct	198 ms	1492 KB	Output is correct
15	Execution timed out	3082 ms	3228 KB	Time limit exceeded
16	Execution timed out	3086 ms	3232 KB	Time limit exceeded
17	Execution timed out	3092 ms	3228 KB	Time limit exceeded
18	Correct	366 ms	2332 KB	Output is correct
19	Execution timed out	3080 ms	3228 KB	Time limit exceeded
20	Execution timed out	3057 ms	3232 KB	Time limit exceeded