Submission #668720

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

                if (a == UINT_MAX)
                    continue;

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

void compute_c_cc()
{
    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;
                }
            }
        }
    }
}

void compute_longest()
{
    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]);
            }
        }
    }
}

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

    compute_c_cc();

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

    longest_route();

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

    compute_c_cc();
    compute_longest();
    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	340 KB	Execution killed with signal 11
5	Correct	1 ms	212 KB	Output is correct
6	Runtime error	2 ms	468 KB	Execution killed with signal 11
7	Correct	4 ms	340 KB	Output is correct
8	Runtime error	3 ms	468 KB	Execution killed with signal 11
9	Correct	6 ms	340 KB	Output is correct
10	Correct	6 ms	392 KB	Output is correct
11	Correct	9 ms	384 KB	Output is correct
12	Runtime error	36 ms	1024 KB	Execution killed with signal 11
13	Runtime error	94 ms	1924 KB	Execution killed with signal 11
14	Correct	196 ms	1620 KB	Output is correct
15	Runtime error	472 ms	4508 KB	Execution killed with signal 11
16	Runtime error	526 ms	4508 KB	Execution killed with signal 11
17	Runtime error	471 ms	4508 KB	Execution killed with signal 11
18	Correct	347 ms	2328 KB	Output is correct
19	Runtime error	567 ms	4504 KB	Execution killed with signal 11
20	Runtime error	579 ms	4504 KB	Execution killed with signal 11