oj.uz

Submission #1018495

# Submission time Handle Problem Language Result Execution time Memory
1018495 2024-07-10T06:19:23 Z MMihalev Sailing Race (CEOI12_race) C++14
85 / 100
 3000 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+=3;
        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;
                            }
                        }
                    }
                }
            }
        }*/
    }
    if(ans==n-1)while(1);
    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;
}

Subtask #1
85.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 4 ms 2908 KB Output is correct
7 Execution timed out 3099 ms 2908 KB Time limit exceeded
8 Correct 5 ms 3164 KB Output is correct
9 Correct 6 ms 3164 KB Output is correct
10 Execution timed out 3055 ms 3164 KB Time limit exceeded
11 Correct 8 ms 3160 KB Output is correct
12 Correct 65 ms 4028 KB Output is correct
13 Correct 177 ms 5376 KB Output is correct
14 Correct 202 ms 6356 KB Output is correct
15 Correct 924 ms 8020 KB Output is correct
16 Incorrect 1082 ms 8016 KB Output isn't correct
17 Correct 942 ms 8016 KB Output is correct
18 Correct 397 ms 8016 KB Output is correct
19 Correct 1212 ms 8044 KB Output is correct
20 Correct 1225 ms 8096 KB Output is correct