Submission #668715

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
668715	2022-12-04T16:47:15 Z	finn__	Sailing Race (CEOI12_race)	C++17	40 / 100	895 ms	6560 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])
            {
                unsigned a = -1;
                for (size_t k = j + 1; k > j || k < i; k++)
                {
                    if (g[k][i])
                    {
                        a = k;
                        break;
                    }
                }

                if (a == UINT_MAX)
                    continue;

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

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	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	Correct	1 ms	212 KB	Output is correct
6	Runtime error	3 ms	456 KB	Execution killed with signal 11
7	Correct	3 ms	340 KB	Output is correct
8	Runtime error	5 ms	596 KB	Execution killed with signal 11
9	Correct	6 ms	340 KB	Output is correct
10	Correct	6 ms	340 KB	Output is correct
11	Correct	9 ms	340 KB	Output is correct
12	Runtime error	59 ms	1392 KB	Execution killed with signal 11
13	Runtime error	171 ms	2576 KB	Execution killed with signal 11
14	Correct	198 ms	1492 KB	Output is correct
15	Runtime error	789 ms	6552 KB	Execution killed with signal 11
16	Runtime error	849 ms	6560 KB	Execution killed with signal 11
17	Runtime error	801 ms	6524 KB	Execution killed with signal 11
18	Correct	348 ms	2328 KB	Output is correct
19	Runtime error	895 ms	6552 KB	Execution killed with signal 11
20	Runtime error	889 ms	6556 KB	Execution killed with signal 11