oj.uz

답안 #668714

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
668714 2022-12-04T16:30:29 Z finn__ Sailing Race (CEOI12_race) C++17
40 / 100
 884 ms 3496 KB 
#include <bits/stdc++.h>
using namespace std;

int main()
{
    size_t n, k;
    cin >> n >> k;

    vector<vector<bool>> g(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;
        }
    }

    vector<vector<unsigned>>
        c(n, vector<unsigned>(n, 0)),
        cc(n, vector<unsigned>(n, 0));
    unsigned max_length = 0, start = -1;

    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;
    }

    vector<vector<unsigned>> longest(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]);
            }
        }
    }
}

Subtask #1
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Unexpected end of file - int32 expected
3 Incorrect 1 ms 304 KB Unexpected end of file - int32 expected
4 Incorrect 1 ms 212 KB Unexpected end of file - int32 expected
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 2 ms 340 KB Unexpected end of file - int32 expected
7 Correct 4 ms 308 KB Output is correct
8 Incorrect 5 ms 360 KB Unexpected end of file - int32 expected
9 Correct 8 ms 340 KB Output is correct
10 Correct 6 ms 340 KB Output is correct
11 Correct 9 ms 400 KB Output is correct
12 Incorrect 59 ms 776 KB Unexpected end of file - int32 expected
13 Incorrect 174 ms 1312 KB Unexpected end of file - int32 expected
14 Correct 193 ms 1740 KB Output is correct
15 Incorrect 786 ms 3436 KB Unexpected end of file - int32 expected
16 Incorrect 834 ms 3496 KB Unexpected end of file - int32 expected
17 Incorrect 787 ms 3340 KB Unexpected end of file - int32 expected
18 Correct 346 ms 2388 KB Output is correct
19 Incorrect 876 ms 3360 KB Unexpected end of file - int32 expected
20 Incorrect 884 ms 3488 KB Unexpected end of file - int32 expected