oj.uz

답안 #1091426

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1091426 2024-09-20T20:20:53 Z vjudge1 Sailing Race (CEOI12_race) C++17
15 / 100
 3000 ms 3348 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)
    {
        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
15.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Incorrect 1 ms 600 KB Output isn't correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Incorrect 2 ms 732 KB Output isn't correct
5 Incorrect 1 ms 604 KB Output isn't correct
6 Incorrect 8 ms 860 KB Output isn't correct
7 Correct 3 ms 860 KB Output is correct
8 Incorrect 19 ms 1028 KB Output isn't correct
9 Incorrect 6 ms 860 KB Output isn't correct
10 Correct 8 ms 860 KB Output is correct
11 Correct 7 ms 860 KB Output is correct
12 Incorrect 859 ms 2132 KB Output isn't correct
13 Execution timed out 3063 ms 3164 KB Time limit exceeded
14 Incorrect 273 ms 2640 KB Output isn't correct
15 Execution timed out 3059 ms 3172 KB Time limit exceeded
16 Execution timed out 3027 ms 3152 KB Time limit exceeded
17 Execution timed out 3043 ms 3344 KB Time limit exceeded
18 Incorrect 473 ms 3156 KB Output isn't correct
19 Execution timed out 3038 ms 3348 KB Time limit exceeded
20 Execution timed out 3052 ms 3308 KB Time limit exceeded