Submission #668721

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
668721	2022-12-04T17:04:52 Z	finn__	Sailing Race (CEOI12_race)	C++17	75 / 100	2575 ms	4352 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;
    }

    compute_longest();
    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

75.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 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	3 ms	304 KB	Output is correct
8	Correct	10 ms	340 KB	Output is correct
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	Incorrect	161 ms	1052 KB	Output isn't correct
13	Correct	457 ms	1760 KB	Output is correct
14	Correct	195 ms	1492 KB	Output is correct
15	Correct	2267 ms	4332 KB	Output is correct
16	Incorrect	2439 ms	4220 KB	Output isn't correct
17	Correct	2288 ms	4252 KB	Output is correct
18	Correct	343 ms	2328 KB	Output is correct
19	Incorrect	2575 ms	4240 KB	Output isn't correct
20	Correct	2569 ms	4352 KB	Output is correct