Submission #1091099

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1091099	2024-09-19T19:40:49 Z	vjudge1	Sailing Race (CEOI12_race)	C++14	100 / 100	837 ms	12492 KB

race

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n, k, i, j, l, r, d, t, u;
    cin >> n >> k;
    vector<vector<long long> > 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] = -99999999;
            else
                dle[l][r] = dri[l][r] = 0;
            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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	356 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	2 ms	440 KB	Output is correct
6	Correct	2 ms	600 KB	Output is correct
7	Correct	3 ms	700 KB	Output is correct
8	Correct	3 ms	604 KB	Output is correct
9	Correct	6 ms	864 KB	Output is correct
10	Correct	6 ms	860 KB	Output is correct
11	Correct	8 ms	948 KB	Output is correct
12	Correct	49 ms	2392 KB	Output is correct
13	Correct	121 ms	4700 KB	Output is correct
14	Correct	148 ms	8024 KB	Output is correct
15	Correct	662 ms	12436 KB	Output is correct
16	Correct	753 ms	12388 KB	Output is correct
17	Correct	648 ms	12344 KB	Output is correct
18	Correct	252 ms	12380 KB	Output is correct
19	Correct	829 ms	12492 KB	Output is correct
20	Correct	837 ms	12376 KB	Output is correct