Submission #1091050

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1091050	2024-09-19T15:35:59 Z	vjudge1	Sailing Race (CEOI12_race)	C++14	75 / 100	879 ms	6632 KB

race

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, k, i, j, l, r, d, t, u;
    cin >> n >> k;
    vector<vector<int> > le(n), ri(n), dle(n), dri(n), pr(n), ne(n);
    vector<vector<bool> > w(n);
    for (i = 0; i < n; i++)
    {
        le[i].resize(n);
        ri[i].resize(n);
        dle[i].resize(n);
        dri[i].resize(n);
        w[i].resize(n);
        pr[i].resize(n);
        ne[i].resize(n);
        for (j = 0; j < n; j++)
            w[i][j] = 0;
        while (1)
        {
            cin >> d;
            if (!d)
                break;
            w[i][d - 1] = 1;
        }
    }
    for (i = 0; i < n; i++)
    {
        for (l = 0; l < n; l++)
        {
            r = (l + i) % n;
            le[l][r] = ri[l][r] = 0;
            if (i)
                dle[l][r] = dri[l][r] = 0;
            else
                dle[l][r] = dri[l][r] = -99999999;
            if (w[l][r])
                dle[l][r] = 1;
            if (w[r][l])
                dri[l][r] = 1;
            for (j = 1; j < i; j++)
            {
                d = (l + j) % n;
                t = max(ri[l][d], le[d][r]) + 1;
                if (w[l][d])
                {
                    le[l][r] = max(le[l][r], t);
                    dle[l][r] = max(dle[l][r], dle[d][r] + 1);
                }
                if (w[r][d])
                {
                    ri[l][r] = max(ri[l][r], t);
                    dri[l][r] = max(dri[l][r], dri[l][d] + 1);
                }
            }
        }
    }
    t = u = 0;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (!w[i][j])
                continue;
            d = max(ri[i][j], le[j][i]) + 1;
            if (d > t)
            {
                t = d;
                u = i;
            }
        }
    }
    if (k)
    {
        for (i = 0; i < n; i++)
        {
            pr[i][i] = ne[i][i] = -1;
            for (j = i + 1;; j++)
            {
                if (j >= n)
                    j -= n;
                if (j == i)
                    break;
                if (w[(j + n - 1) % n][i])
                    pr[i][j] = (j + n - 1) % n;
                else
                    pr[i][j] = pr[i][(j + n - 1) % n];
            }
            for (j = i - 1;; j--)
            {
                if (j < 0)
                    j += n;
                if (j == i)
                    break;
                if (w[(j + 1) % n][i])
                    ne[i][j] = (j + 1) % n;
                else
                    ne[i][j] = ne[i][(j + 1) % n];
            }
        }
        for (j = 0; j < n; j++)
        {
            for (l = 0; l < n; l++)
            {
                if (l == j)
                    continue;
                i = pr[j][l];
                if (i != -1)
                {
                    for (r = j + 1;; r++)
                    {
                        if (r >= n)
                            r -= n;
                        if (r == i)
                            break;
                        if (!w[l][r])
                            continue;
                        d = max(ri[j][r], le[r][i]) + dri[l][j] + 2;
                        if (d > t)
                        {
                            t = d;
                            u = i;
                        }
                    }
                }
                i = ne[j][l];
                if (i != -1)
                {
                    for (r = i + 1;; r++)
                    {
                        if (r >= n)
                            r -= n;
                        if (r == j)
                            break;
                        if (!w[l][r])
                            continue;
                        d = max(ri[i][r], le[r][j]) + dle[j][l] + 2;
                        if (d > t)
                        {
                            t = d;
                            u = i;
                        }
                    }
                }
            }
        }
    }
    cout << t << "\n" << u + 1;
    return 0;
}

Subtask #1

75.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Incorrect	1 ms	348 KB	Output isn't correct
5	Correct	2 ms	348 KB	Output is correct
6	Correct	2 ms	348 KB	Output is correct
7	Correct	3 ms	348 KB	Output is correct
8	Correct	4 ms	612 KB	Output is correct
9	Correct	7 ms	600 KB	Output is correct
10	Correct	5 ms	600 KB	Output is correct
11	Correct	9 ms	604 KB	Output is correct
12	Incorrect	51 ms	1372 KB	Output isn't correct
13	Incorrect	133 ms	2648 KB	Output isn't correct
14	Correct	148 ms	4188 KB	Output is correct
15	Correct	677 ms	6492 KB	Output is correct
16	Correct	774 ms	6592 KB	Output is correct
17	Incorrect	675 ms	6492 KB	Output isn't correct
18	Correct	275 ms	6496 KB	Output is correct
19	Correct	879 ms	6624 KB	Output is correct
20	Incorrect	865 ms	6632 KB	Output isn't correct