oj.uz

답안 #1091429

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1091429 2024-09-20T20:30:03 Z Jovica Sailing Race (CEOI12_race) C++14
20 / 100
 701 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];

    //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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Incorrect 1 ms 600 KB Output isn't correct
5 Incorrect 1 ms 716 KB Output isn't correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Incorrect 3 ms 856 KB Output isn't correct
9 Incorrect 5 ms 968 KB Output isn't correct
10 Correct 8 ms 860 KB Output is correct
11 Correct 7 ms 856 KB Output is correct
12 Incorrect 39 ms 1368 KB Output isn't correct
13 Incorrect 110 ms 2168 KB Output isn't correct
14 Incorrect 247 ms 2644 KB Output isn't correct
15 Incorrect 592 ms 3020 KB Output isn't correct
16 Incorrect 623 ms 3156 KB Output isn't correct
17 Incorrect 606 ms 3156 KB Output isn't correct
18 Incorrect 438 ms 3156 KB Output isn't correct
19 Incorrect 701 ms 3156 KB Output isn't correct
20 Incorrect 645 ms 3156 KB Output isn't correct