Submission #1016549

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1016549	2024-07-08T08:03:23 Z	MMihalev	Sailing Race (CEOI12_race)	C++17	0 / 100	1033 ms	6996 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<n-1;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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	348 KB	Output isn't 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	600 KB	Output isn't correct
5	Incorrect	1 ms	2900 KB	Output isn't correct
6	Incorrect	2 ms	2788 KB	Output isn't correct
7	Incorrect	3 ms	2652 KB	Output isn't correct
8	Incorrect	3 ms	2908 KB	Output isn't correct
9	Incorrect	8 ms	2792 KB	Output isn't correct
10	Incorrect	7 ms	2852 KB	Output isn't correct
11	Incorrect	12 ms	2908 KB	Output isn't correct
12	Incorrect	62 ms	3768 KB	Output isn't correct
13	Incorrect	164 ms	4948 KB	Output isn't correct
14	Incorrect	346 ms	5968 KB	Output isn't correct
15	Incorrect	784 ms	6740 KB	Output isn't correct
16	Incorrect	902 ms	6736 KB	Output isn't correct
17	Incorrect	873 ms	6996 KB	Output isn't correct
18	Incorrect	536 ms	6724 KB	Output isn't correct
19	Incorrect	1020 ms	6736 KB	Output isn't correct
20	Incorrect	1033 ms	6992 KB	Output isn't correct