oj.uz

답안 #1091454

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1091454 2024-09-20T22:15:56 Z vjudge1 Sailing Race (CEOI12_race) C++17
0 / 100
 3000 ms 3412 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);
        }
    }

    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;

    //cout<< A<<" "<<B<<" "<<C<<" "<<D<<"\n1+"<<x-y-1-1<<"+1+"<<y<<endl<<"x="<<x<<endl;

    if (x>odg)
    {
        //cout<<"ulava\n";
        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;
        }
        //cout<< "za i="<<i<< " odg = "<<x<<endl;
    }

    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        {
            f(i,j,i);
            f(i,j,j);
        }

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


    sredi_intervali();

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

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

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

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

*/

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Incorrect 2 ms 692 KB Output isn't correct
5 Incorrect 5 ms 860 KB Output isn't correct
6 Incorrect 10 ms 860 KB Output isn't correct
7 Incorrect 27 ms 932 KB Output isn't correct
8 Incorrect 20 ms 1112 KB Output isn't correct
9 Incorrect 61 ms 1108 KB Output isn't correct
10 Incorrect 102 ms 1360 KB Output isn't correct
11 Incorrect 98 ms 1324 KB Output isn't correct
12 Incorrect 913 ms 2332 KB Output isn't correct
13 Execution timed out 3062 ms 2900 KB Time limit exceeded
14 Execution timed out 3067 ms 2896 KB Time limit exceeded
15 Execution timed out 3055 ms 3352 KB Time limit exceeded
16 Execution timed out 3015 ms 3152 KB Time limit exceeded
17 Execution timed out 3068 ms 3400 KB Time limit exceeded
18 Execution timed out 3055 ms 3412 KB Time limit exceeded
19 Execution timed out 3025 ms 3376 KB Time limit exceeded
20 Execution timed out 3055 ms 3412 KB Time limit exceeded