답안 #668720

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
668720 2022-12-04T17:04:12 Z finn__ Sailing Race (CEOI12_race) C++17
40 / 100
579 ms 4508 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 + 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';
}
# 결과 실행 시간 메모리 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