oj.uz

Submission #1091431

# Submission time Handle Problem Language Result Execution time Memory
1091431 2024-09-20T20:56:13 Z vjudge1 Sailing Race (CEOI12_race) C++17
20 / 100
 656 ms 3156 KB 
#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);
        }
        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;
            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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 0 ms 604 KB Output isn't correct
4 Incorrect 1 ms 604 KB Output isn't correct
5 Incorrect 1 ms 604 KB Output isn't correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Incorrect 3 ms 900 KB Output isn't correct
9 Incorrect 5 ms 860 KB Output isn't correct
10 Correct 8 ms 984 KB Output is correct
11 Correct 7 ms 1016 KB Output is correct
12 Incorrect 39 ms 1372 KB Output isn't correct
13 Incorrect 127 ms 2088 KB Output isn't correct
14 Incorrect 243 ms 2644 KB Output isn't correct
15 Incorrect 577 ms 3016 KB Output isn't correct
16 Incorrect 613 ms 3132 KB Output isn't correct
17 Incorrect 580 ms 3048 KB Output isn't correct
18 Incorrect 456 ms 3108 KB Output isn't correct
19 Incorrect 656 ms 3156 KB Output isn't correct
20 Incorrect 646 ms 3156 KB Output isn't correct