Submission #1091429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091429		Jovica	Sailing Race (CEOI12_race)	C++14	20 / 100	701 ms	3156 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];

    //cout<< "l="<<l<<" r="<<r<<" poz="<<poz<<endl;
    //system("pause");
    //cout<<endl;

    int odg = 0;
    for (int sosed = l+1;sosed!=r;sosed++)
    {
        if (sosed>n) sosed = 1;
        if (r == sosed) break;
        if (mat[poz][sosed])
        {
            odg = max(f(l,sosed,sosed)+1,odg);
            odg = max(f(sosed,r,sosed)+1,odg);
        }
        else{
            odg = max(odg,f(l,sosed,l));
        }
    }

    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)
        {
            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;

    if (x>odg)
    {
        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;
        }
    }

    if (m==0 || true)
    {
        cout<<odg<<endl<<p<<endl;
        return 0;
    }



    sredi_intervali();

    for (int B=1;B<=n;B++)
    {
        //cout<<"ulava u B="<<B<<endl;
        int C = B+1;
        if (C>n) C=1;
        while(C!=B)
        {
            int A = C+1;
            if (A>n) A=1;
            while(A!=B)
            {
                if (mat[A][B]==true) break;

                A++;
                if (A>n) A=1;
            }

            if (A!=B)
            {
                int D = A+1;
                if (D>n) D=1;
                while(D!=B)
                {
                    if (mat[C][D]==true)
                    {
                        presmetaj(A,B,C,D,true);
                    }
                    D++;
                    if (D>n) D=1;
                }
            }

            C++;
            if (C>n) C=1;
        }

        /// sea counter klakwajs
        C = B-1;
        if (C==0) C=n;
        while(C!=B)
        {
            int A = C-1;
            if (A==0) A=n;
            while(A!=B)
            {
                if (mat[A][B]==true) break;

                A--;
                if (A==0) A=n;
            }

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

            C--;
            if (C==0) C=n;
        }
    }

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

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

*/

• Subtask 1: 20 / 100