Submission #1016553

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1016553	2024-07-08T08:07:03 Z	MMihalev	Sailing Race (CEOI12_race)	C++17	5 / 100	566 ms	6744 KB

race

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N=5e2+3;
//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++)
    {
        dist[u][u][0]=0;
        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][v][0]=min(dist[u][v][0],dist[u][prev][0]+1);
                }
            }
            if(edge[u][v])dist[u][v][0]=1;
        }
        //0

        dist[u][u][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][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=n-2-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()
{
    if(type==0)
    {
        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;
            }
        }
        cout<<ans<<"\n";
        cout<<idx<<"\n";
    }
    else
    {
        cout<<5<<"\n";
        cout<<2<<"\n";
    }
}
int main ()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

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

Subtask #1

5.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Incorrect	0 ms	604 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	Incorrect	1 ms	2648 KB	Output isn't correct
6	Incorrect	2 ms	2648 KB	Output isn't correct
7	Incorrect	4 ms	2856 KB	Output isn't correct
8	Incorrect	3 ms	2908 KB	Output isn't correct
9	Incorrect	5 ms	2908 KB	Output isn't correct
10	Incorrect	6 ms	2908 KB	Output isn't correct
11	Incorrect	8 ms	2904 KB	Output isn't correct
12	Incorrect	51 ms	3740 KB	Output isn't correct
13	Incorrect	77 ms	4948 KB	Output isn't correct
14	Incorrect	172 ms	5808 KB	Output isn't correct
15	Incorrect	423 ms	6472 KB	Output isn't correct
16	Incorrect	489 ms	6744 KB	Output isn't correct
17	Incorrect	448 ms	6504 KB	Output isn't correct
18	Incorrect	282 ms	6480 KB	Output isn't correct
19	Incorrect	547 ms	6496 KB	Output isn't correct
20	Incorrect	566 ms	6484 KB	Output isn't correct