Submission #1091432

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1091432	2024-09-20T20:59:20 Z	vjudge1	Sailing Race (CEOI12_race)	C++17	40 / 100	384 ms	3156 KB

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

    int odg = 0, p = 0;
    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;
    }

    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

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Incorrect	1 ms	348 KB	Output isn't correct
3	Incorrect	1 ms	604 KB	Output isn't correct
4	Incorrect	1 ms	604 KB	Output isn't correct
5	Correct	1 ms	716 KB	Output is correct
6	Incorrect	1 ms	604 KB	Output isn't correct
7	Correct	3 ms	860 KB	Output is correct
8	Incorrect	2 ms	896 KB	Output isn't correct
9	Correct	4 ms	856 KB	Output is correct
10	Correct	10 ms	1040 KB	Output is correct
11	Correct	6 ms	856 KB	Output is correct
12	Incorrect	20 ms	1368 KB	Output isn't correct
13	Incorrect	44 ms	2056 KB	Output isn't correct
14	Correct	89 ms	2652 KB	Output is correct
15	Incorrect	266 ms	3152 KB	Output isn't correct
16	Incorrect	351 ms	3092 KB	Output isn't correct
17	Incorrect	264 ms	3156 KB	Output isn't correct
18	Correct	123 ms	3156 KB	Output is correct
19	Incorrect	384 ms	3156 KB	Output isn't correct
20	Incorrect	366 ms	3156 KB	Output isn't correct