Submission #668723

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
668723	2022-12-04T17:07:59 Z	finn__	Sailing Race (CEOI12_race)	C++17	65 / 100	2698 ms	4340 KB

race

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

size_t n;
bool swapped = 0;
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 = swapped ? (n - (a % n)) : (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;
    }

    compute_longest();
    longest_route();

    for (size_t i = 0; i < n / 2; i++)
        swap(g[i], g[n - i - 1]);

    swapped = 1;
    compute_c_cc();
    compute_longest();
    longest_route();

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

Subtask #1

65.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Incorrect	2 ms	212 KB	Output isn't correct
5	Correct	1 ms	212 KB	Output is correct
6	Incorrect	6 ms	340 KB	Output isn't correct
7	Correct	4 ms	340 KB	Output is correct
8	Correct	11 ms	340 KB	Output is correct
9	Correct	8 ms	340 KB	Output is correct
10	Correct	8 ms	392 KB	Output is correct
11	Correct	9 ms	388 KB	Output is correct
12	Incorrect	165 ms	892 KB	Output isn't correct
13	Correct	503 ms	1764 KB	Output is correct
14	Correct	221 ms	1596 KB	Output is correct
15	Correct	2348 ms	4328 KB	Output is correct
16	Incorrect	2496 ms	4324 KB	Output isn't correct
17	Incorrect	2394 ms	4340 KB	Output isn't correct
18	Correct	367 ms	2332 KB	Output is correct
19	Incorrect	2698 ms	4324 KB	Output isn't correct
20	Incorrect	2683 ms	4328 KB	Output isn't correct