oj.uz

Submission #1018497

# Submission time Handle Problem Language Result Execution time Memory
1018497 2024-07-10T06:20:02 Z MMihalev Sailing Race (CEOI12_race) C++14
95 / 100
 1227 ms 8348 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-2)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
95.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 856 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2776 KB Output is correct
6 Correct 3 ms 2908 KB Output is correct
7 Correct 3 ms 3164 KB Output is correct
8 Correct 5 ms 3164 KB Output is correct
9 Correct 6 ms 3160 KB Output is correct
10 Correct 5 ms 3164 KB Output is correct
11 Correct 8 ms 3164 KB Output is correct
12 Correct 65 ms 4188 KB Output is correct
13 Correct 170 ms 5456 KB Output is correct
14 Correct 198 ms 6224 KB Output is correct
15 Correct 920 ms 8100 KB Output is correct
16 Incorrect 1096 ms 8016 KB Output isn't correct
17 Correct 1008 ms 8096 KB Output is correct
18 Correct 327 ms 8016 KB Output is correct
19 Correct 1208 ms 8096 KB Output is correct
20 Correct 1227 ms 8348 KB Output is correct