Submission #668722

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
668722	2022-12-04T17:06:29 Z	finn__	Sailing Race (CEOI12_race)	C++17	75 / 100	2559 ms	4400 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();

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

    swapped = 1;
    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	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	2 ms	324 KB	Output is correct
6	Incorrect	6 ms	368 KB	Output isn't correct
7	Correct	3 ms	340 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	388 KB	Output is correct
11	Correct	9 ms	388 KB	Output is correct
12	Incorrect	166 ms	952 KB	Output isn't correct
13	Correct	506 ms	1760 KB	Output is correct
14	Correct	205 ms	1600 KB	Output is correct
15	Correct	2309 ms	4348 KB	Output is correct
16	Incorrect	2467 ms	4324 KB	Output isn't correct
17	Correct	2241 ms	4380 KB	Output is correct
18	Correct	348 ms	2332 KB	Output is correct
19	Incorrect	2557 ms	4256 KB	Output isn't correct
20	Correct	2559 ms	4400 KB	Output is correct