Submission #1091459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091459		vjudge1	Sailing Race (CEOI12_race)	C++17	5 / 100	3087 ms	3524 KiB

race

#include <bits/stdc++.h>

using namespace std;
int n,m;
vector<vector<int> > adj(501);

/// levo, desno, dali sme kaj levio element ili desnio, clockwise
bool visited[501][501][2];
int dp[501][501][2];
bool mat[501][501];

int f(int l,int r,int poz)
{
    bool t = (l==poz);
    if (visited[l][r][t]) return dp[l][r][t];

    int odg = 0;
    for (int sosed = l+1;sosed!=r;sosed++)
    {
        if (sosed>n) sosed = 1;
        if (r == sosed) break;

        if (l<r)
        {
            if ((l<sosed && sosed<r)==false) break;
        }
        if (r<l)
        {
            if ((l<sosed && sosed<r)==true) break;
        }

        if (mat[poz][sosed])
        {
            odg = max(f(l,sosed,sosed)+1,odg);
            odg = max(f(sosed,r,sosed)+1,odg);
        }
    }

    visited[l][r][t] = true;
    dp[l][r][t] = odg;
    //if (l==7 && r==2 && t) cout<< "depeto vika "<<odg<<endl;
    return odg;
}

bool dolgvisited1[501][501];
int dolgdp1[501][501];
bool dolgvisited2[501][501];
int dolgdp2[501][501];

bool poseteno[501];
int kolku[501];
int pocetok, kraj;

int f1(int poz)
{
    if (poz == kraj) return 0;
    if (poseteno[poz]) return kolku[poz];
    int sosed = poz+1;
    int d = -10000;
    while(true)
    {
        if (sosed>n) sosed = 1;

        if (sosed==kraj)
        {
            if (mat[poz][sosed]) d = max(d,1);
            break;
        }
        if (mat[poz][sosed]) d = max(d,f1(sosed)+1);

        sosed++;
    }

    poseteno[poz] = true;
    kolku[poz] = d;
    return d;
}

int f2(int poz)
{
    if (poz == kraj) return 0;
    if (poseteno[poz]) return kolku[poz];
    int sosed = poz-1;
    int d = -10000;
    while(true)
    {
        if (sosed==0) sosed = n;

        if (sosed==kraj)
        {
            if(mat[poz][sosed]) d = max(d,1);
            break;
        }
        if (mat[poz][sosed]) d = max(d,f2(sosed)+1);

        sosed--;
    }

    poseteno[poz] = true;
    kolku[poz] = d;
    return d;
}

void sredi_intervali()
{
    for (pocetok = 1;pocetok<=n;pocetok++)
        for (kraj=1;kraj<=n;kraj++)
        {
            memset(poseteno,0,sizeof(poseteno));
            dolgdp1[pocetok][kraj] = f1(pocetok);

            //cout<<"od "<<pocetok<< " do "<<kraj<<" - "<<dolgdp1[pocetok][kraj]<<endl;
        }

    for (pocetok = 1;pocetok<=n;pocetok++)
        for (kraj=1;kraj<=n;kraj++)
        {
            memset(poseteno,0,sizeof(poseteno));
            dolgdp2[pocetok][kraj] = f2(pocetok);
        }
}

int odg = 0, p = 0;
void presmetaj(int A,int B,int C,int D,bool eden)
{
    //cout<<"ulava za "<<A<<" "<<B<<" "<<C<< " "<<D<<" eden="<<eden<<endl;

    int x = 0;
    if (eden)
    {
        x= 1 + dolgdp1[B][C]+ 1;
    }
    else
    {
        x = 1 + dolgdp2[B][C] + 1;
    }
    int y = max(dp[D][A][true], dp[D][B][true]);

    x += y;

    //cout<< A<<" "<<B<<" "<<C<<" "<<D<<"\n1+"<<x-y-1-1<<"+1+"<<y<<endl<<"x="<<x<<endl;

    if (x>odg)
    {
        //cout<<"ulava\n";
        odg = x;
        p = A;
    }
}

int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        int a;
        while(true)
        {
            cin>>a;
            if (a==0) break;
            //adj[i].push_back(a);
            mat[i][a] = true;
        }
    }

    for (int i=1;i<=n;i++)
    {
        int x = f(i,i,i);

        if (x>odg)
        {
            odg = x;
            p = i;
        }
        //cout<< "za i="<<i<< " odg = "<<x<<endl;
    }

    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        {
            f(i,j,i);
            f(i,j,j);
        }

    //cout<<odg<<endl<<p<<endl;
    //return 0;


    sredi_intervali();

    for (int B=1;B<=n;B++)
    {
        int A = B+1;
        if (A == n+1) A = 1;
        for (int C=B+1;C!=B;C++)
        {
            if (C == n+1) C = 1;
            if (C==B) break;
            if (A==C) {
                while (A!=B)
                {
                    A++;
                    if (A==n+1) A = 1;
                    if (A==B) break;
                    if (mat[A][B]) break;
                }
            }
            if (A==B) break;
            for (int D = A+1; D!=B; D++)
            {
                if (D==n+1) D = 1;
                if (D==B)  break;
                if (mat[A][B] && mat[C][D])
                    presmetaj(A,B,C,D,1);
            }
        }


        A = B-1;
        if (A==0) A = n;
        for (int C=B-1;C!=B;C--)
        {
            if (C == 0) C = n;
            if (C==B) break;
            if (A==C) {
                while (A!=B)
                {
                    A--;
                    if (A==0) A = n;
                    if (A==B) break;
                    if (mat[A][B]) break;
                }
            }
            if (A==B) break;
            for (int D = A-1; D!=B; D--)
            {
                if (D==0) D = n;
                if (D==B)  break;
                if (mat[A][B] && mat[C][D])
                    presmetaj(A,B,C,D,0);
            }
        }
    }

    cout<<odg<<endl<<p;
    return 0;
}
/*

7 1
5 0
5 0
7 0
3 0
4 0
4 3 0
2 1 0



4 1
3 0
0
4 0
2 0

*/

• Subtask 1: 5 / 100