oj.uz

Submission #1018485

# Submission time Handle Problem Language Result Execution time Memory
1018485 2024-07-10T06:15:43 Z MMihalev Sailing Race (CEOI12_race) C++14
40 / 100
 1402 ms 8096 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++)
            {
                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=0;
    int idx=1;
    for(int u=1;u<=n;u++)
    {
        if(dp[u][n-1][0]>ans)
        {
            ans=dp[u][n-1][0];
            idx=u;
        }
    }
    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;
                        }
                    }
                }
            }
        }

        //shit
        idx+=2;
        for(int dir=0;dir<2;dir++)
        {
            for(int T=1;T<=n;T++)
            {
                int idS;
                for(int i=0;i<n-1;i++)
                {
                    int Y=track[T][dir][i];
                    if(Y==idx)idS=i;
                }

                for(int i=idS+1;i<n-1;i++)
                {
                    int Y=track[T][dir][i];

                    for(int j=idS-1;j>=0;j--)
                    {
                        int X=track[T][dir][j];

                        if(dist[T][X][dir]!=1e9 && edge[X][Y] && edge[idx][T])
                        {
                            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;
                            }
                        }
                    }
                }
            }
        }
    }

    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:161:21: warning: 'idS' may be used uninitialized in this function [-Wmaybe-uninitialized]
  161 |                 int idS;
      |                     ^~~

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 604 KB Output isn't correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Incorrect 1 ms 2908 KB Output isn't correct
5 Correct 1 ms 2908 KB Output is correct
6 Incorrect 3 ms 3048 KB Output isn't correct
7 Correct 3 ms 3144 KB Output is correct
8 Incorrect 5 ms 3160 KB Output isn't correct
9 Correct 6 ms 3292 KB Output is correct
10 Correct 5 ms 3164 KB Output is correct
11 Correct 8 ms 3188 KB Output is correct
12 Incorrect 90 ms 4176 KB Output isn't correct
13 Incorrect 190 ms 5460 KB Output isn't correct
14 Correct 204 ms 6456 KB Output is correct
15 Incorrect 1026 ms 8016 KB Output isn't correct
16 Incorrect 1194 ms 8096 KB Output isn't correct
17 Incorrect 1048 ms 8096 KB Output isn't correct
18 Correct 339 ms 8016 KB Output is correct
19 Incorrect 1338 ms 8096 KB Output isn't correct
20 Incorrect 1402 ms 8068 KB Output isn't correct