Submission #1091100

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1091100	2024-09-19T19:41:33 Z	vjudge1	Sailing Race (CEOI12_race)	C++14	100 / 100	872 ms	6656 KB

race

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    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] = -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++)
        {
            for (j = 0; j < n; j++)
                pr[i][j] = ne[i][j] = -1;
            for (j = n - 1; j >= 0; j--)
            {
                if (w[j][i])
                {
                    pr[i][0] = j;
                    break;
                }
            }
            for (j = 1; j < n; j++)
            {
                if (w[j - 1][i])
                    pr[i][j] = j - 1;
                else
                    pr[i][j] = pr[i][j - 1];
            }
            for (j = 0; j < n; j++)
            {
                if (w[j][i])
                {
                    ne[i][n - 1] = j;
                    break;
                }
            }
            for (j = n - 2; j >= 0; j--)
            {
                if (w[j + 1][i])
                    ne[i][j] = j + 1;
                else
                    ne[i][j] = ne[i][j + 1];
            }
        }
        for (j = 0; j < n; j++)
        {
            if (pr[j][0] == -1)
                continue;
            for (l = 0; l < n; l++)
            {
                if (l == j)
                    continue;
                i = pr[j][l];
                if (i != l && (i + n - j) % n + (l + n - i) % n == (l + n - j) % n)
                {
                    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 != l && (i + n - l) % n + (j + n - i) % n == (j + n - l) % n)
                {
                    i = ne[j][l];
                    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	1 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	1 ms	348 KB	Output is correct
6	Correct	2 ms	564 KB	Output is correct
7	Correct	3 ms	352 KB	Output is correct
8	Correct	3 ms	604 KB	Output is correct
9	Correct	5 ms	464 KB	Output is correct
10	Correct	4 ms	604 KB	Output is correct
11	Correct	8 ms	604 KB	Output is correct
12	Correct	50 ms	1460 KB	Output is correct
13	Correct	130 ms	2648 KB	Output is correct
14	Correct	141 ms	4184 KB	Output is correct
15	Correct	690 ms	6592 KB	Output is correct
16	Correct	769 ms	6628 KB	Output is correct
17	Correct	667 ms	6592 KB	Output is correct
18	Correct	241 ms	6488 KB	Output is correct
19	Correct	862 ms	6648 KB	Output is correct
20	Correct	872 ms	6656 KB	Output is correct