Submission #1091100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091100		vjudge1	Sailing Race (CEOI12_race)	C++14	100 / 100	872 ms	6656 KiB

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 / 100