oj.uz

Submission #1091085

# Submission time Handle Problem Language Result Execution time Memory
1091085 2024-09-19T17:31:22 Z vjudge1 Sailing Race (CEOI12_race) C++17
40 / 100
 394 ms 3408 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)
{
    //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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is 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 Correct 1 ms 604 KB Output is correct
6 Incorrect 1 ms 604 KB Output isn't correct
7 Correct 3 ms 604 KB Output is correct
8 Incorrect 2 ms 860 KB Output isn't correct
9 Correct 4 ms 856 KB Output is correct
10 Correct 10 ms 860 KB Output is correct
11 Correct 7 ms 860 KB Output is correct
12 Incorrect 22 ms 1372 KB Output isn't correct
13 Incorrect 49 ms 2036 KB Output isn't correct
14 Correct 97 ms 2392 KB Output is correct
15 Incorrect 297 ms 3152 KB Output isn't correct
16 Incorrect 347 ms 3056 KB Output isn't correct
17 Incorrect 299 ms 3152 KB Output isn't correct
18 Correct 143 ms 3152 KB Output is correct
19 Incorrect 391 ms 3156 KB Output isn't correct
20 Incorrect 394 ms 3408 KB Output isn't correct