oj.uz

Submission #1018529

# Submission time Handle Problem Language Result Execution time Memory
1018529 2024-07-10T06:32:04 Z MMihalev Sailing Race (CEOI12_race) C++14
0 / 100
 693 ms 8244 KB 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N=6e2+10;
//0 clockwise
//1 counterclockwise
vector<int>track[MAX_N][2];//0 - ; 1 +
int n;
bool edge[MAX_N][MAX_N];
int type;
int dp[MAX_N][MAX_N][2];
int dist[MAX_N][MAX_N][2];//0 - ; 1 +
void precompute()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            track[i][0].push_back(j);
        }
        for(int j=1;j<i;j++)
        {
            track[i][0].push_back(j);
        }
        //0

        for(int j=i-1;j>=1;j--)
        {
            track[i][1].push_back(j);
        }
        for(int j=n;j>i;j--)
        {
            track[i][1].push_back(j);
        }
        //1
    }
    ///track


    for(int u=1;u<=n;u++)
    {
        for(int j=0;j<n-1;j++)
        {
            int v=track[u][0][j];
            dist[u][v][0]=1e9;
            for(int r=0;r<j;r++)
            {
                int prev=track[u][0][r];
                if(edge[prev][v] && dist[u][prev][0]!=1e9)
                {
                    dist[u][v][0]=min(dist[u][v][0],dist[u][prev][0]+1);
                }
            }
            if(edge[u][v])dist[u][v][0]=1;
        }
        //0

        for(int j=0;j<n-1;j++)
        {
            int v=track[u][1][j];
            dist[u][v][1]=1e9;
            for(int r=0;r<j;r++)
            {
                int prev=track[u][1][r];
                if(edge[prev][v] && dist[u][prev][1]!=1e9)
                {
                    dist[u][v][1]=min(dist[u][v][1],dist[u][prev][1]+1);
                }
            }
            if(edge[u][v])dist[u][v][1]=1;
        }
        //1
    }
    ///dist

    for(int used=1;used<n;used++)
    {
        for(int dir=0;dir<2;dir++)
        {
            for(int u=1;u<=n;u++)
            {
                dp[u][used][dir]=dp[u][used-1][dir];
                for(int i=0;i<used;i++)
                {
                    int v=track[u][dir][i];
                    int pref=i;
                    int suf=used-1-i;

                    if(edge[u][v])dp[u][used][dir]=max(dp[u][used][dir],max(dp[v][suf][dir],dp[v][pref][1-dir])+1);
                }
            }
        }
    }
    ///dp
}
void read()
{
    cin>>n>>type;
    for(int u=1;u<=n;u++)
    {
        int v;
        cin>>v;
        while(v!=0)
        {
            edge[u][v]=1;
            cin>>v;
        }
    }
}
void solve()
{
    int ans=-1;
    int idx=1;
    for(int u=1;u<=n;u++)
    {
        if(max(dp[u][n-1][0],dp[u][n-1][1])>=ans)
        {
            ans=dp[u][n-1][0];
            idx=u;
        }
    }
    int prevans=ans;
    return;
    if(type==1)
    {
        for(int dir=0;dir<2;dir++)
        {
            for(int T=1;T<=n;T++)
            {
                for(int i=0;i<n-1;i++)
                {
                    int Y=track[T][dir][i];
                    int S=-10;
                    int idS=-1;
                    for(int j=i-1;j>=0;j--)
                    {
                        int X=track[T][dir][j];
                        if(S!=-10 && dist[T][X][dir]!=1e9 && edge[X][Y])
                        {
                            int currer=1+dist[T][X][dir]+1+max(dp[Y][n-2-i][dir],dp[Y][i-idS-1][1-dir]);
                            if(currer>ans)
                            {
                                ans=currer;
                                idx=S;
                            }
                        }
                        if(edge[X][T])
                        {
                            S=X;
                            idS=j;
                        }
                    }
                }
            }
        }
    }
    if(n>=500)
    {

    }
    cout<<ans<<"\n";
    cout<<idx<<"\n";
}
int main ()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    read();
    precompute();
    solve();
    return 0;
}

Compilation message

race.cpp: In function 'void solve()':
race.cpp:123:9: warning: unused variable 'prevans' [-Wunused-variable]
  123 |     int prevans=ans;
      |         ^~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Unexpected end of file - int32 expected
2 Incorrect 0 ms 604 KB Unexpected end of file - int32 expected
3 Incorrect 1 ms 768 KB Unexpected end of file - int32 expected
4 Incorrect 1 ms 2908 KB Unexpected end of file - int32 expected
5 Incorrect 1 ms 2908 KB Unexpected end of file - int32 expected
6 Incorrect 2 ms 2908 KB Unexpected end of file - int32 expected
7 Incorrect 3 ms 2908 KB Unexpected end of file - int32 expected
8 Incorrect 3 ms 3164 KB Unexpected end of file - int32 expected
9 Incorrect 5 ms 3164 KB Unexpected end of file - int32 expected
10 Incorrect 5 ms 3164 KB Unexpected end of file - int32 expected
11 Incorrect 8 ms 3164 KB Unexpected end of file - int32 expected
12 Incorrect 42 ms 4028 KB Unexpected end of file - int32 expected
13 Incorrect 112 ms 5460 KB Unexpected end of file - int32 expected
14 Incorrect 193 ms 6360 KB Unexpected end of file - int32 expected
15 Incorrect 506 ms 7856 KB Unexpected end of file - int32 expected
16 Incorrect 603 ms 8016 KB Unexpected end of file - int32 expected
17 Incorrect 532 ms 8244 KB Unexpected end of file - int32 expected
18 Incorrect 349 ms 8016 KB Unexpected end of file - int32 expected
19 Incorrect 693 ms 7844 KB Unexpected end of file - int32 expected
20 Incorrect 658 ms 7860 KB Unexpected end of file - int32 expected