답안 #668717

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
668717 2022-12-04T16:51:52 Z finn__ Sailing Race (CEOI12_race) C++17
40 / 100
3000 ms 3232 KB
#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 % n) + 1; k > (j % n) || (k % n) < i; k++)
                {
                    if (g[j % n][i])
                    {
                        a = k % n;
                        break;
                    }
                }

                if (a == UINT_MAX)
                    continue;

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

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';
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 3075 ms 212 KB Time limit exceeded
3 Execution timed out 3076 ms 212 KB Time limit exceeded
4 Execution timed out 3091 ms 212 KB Time limit exceeded
5 Correct 2 ms 212 KB Output is correct
6 Execution timed out 3076 ms 340 KB Time limit exceeded
7 Correct 4 ms 340 KB Output is correct
8 Execution timed out 3077 ms 340 KB Time limit exceeded
9 Correct 7 ms 340 KB Output is correct
10 Correct 6 ms 308 KB Output is correct
11 Correct 10 ms 388 KB Output is correct
12 Execution timed out 3066 ms 764 KB Time limit exceeded
13 Execution timed out 3077 ms 1284 KB Time limit exceeded
14 Correct 198 ms 1492 KB Output is correct
15 Execution timed out 3082 ms 3228 KB Time limit exceeded
16 Execution timed out 3086 ms 3232 KB Time limit exceeded
17 Execution timed out 3092 ms 3228 KB Time limit exceeded
18 Correct 366 ms 2332 KB Output is correct
19 Execution timed out 3080 ms 3228 KB Time limit exceeded
20 Execution timed out 3057 ms 3232 KB Time limit exceeded