Submission #1090436

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1090436	2024-09-18T11:01:56 Z	vjudge1	Sailing Race (CEOI12_race)	C++14	75 / 100	878 ms	6460 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] = -1;
            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	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Incorrect	1 ms	344 KB	Output isn't correct
5	Correct	2 ms	348 KB	Output is correct
6	Correct	2 ms	344 KB	Output is correct
7	Correct	3 ms	348 KB	Output is correct
8	Correct	3 ms	604 KB	Output is correct
9	Correct	6 ms	600 KB	Output is correct
10	Correct	5 ms	604 KB	Output is correct
11	Correct	8 ms	600 KB	Output is correct
12	Incorrect	50 ms	1372 KB	Output isn't correct
13	Incorrect	143 ms	2392 KB	Output isn't correct
14	Correct	168 ms	4296 KB	Output is correct
15	Correct	694 ms	6232 KB	Output is correct
16	Correct	836 ms	6452 KB	Output is correct
17	Incorrect	684 ms	6236 KB	Output isn't correct
18	Correct	263 ms	6236 KB	Output is correct
19	Correct	878 ms	6460 KB	Output is correct
20	Incorrect	860 ms	6460 KB	Output isn't correct