제출 #1091085

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1091085		vjudge1	Sailing Race (CEOI12_race)	C++17	40 / 100	394 ms	3408 KiB

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)
{
    //cout<< "l="<<l<<" r="<<r<<" poz="<<poz<<endl;
    //system("pause");
    //cout<<endl;
    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;
    return odg;
}

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;
}
/*

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

*/

• Subtask 1: 40 / 100