Submission #1016558

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1016558	2024-07-08T08:08:07 Z	MMihalev	Sailing Race (CEOI12_race)	C++14	40 / 100	581 ms	6512 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=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()
{
    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

40.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	1 ms	604 KB	Output isn't correct
4	Incorrect	1 ms	604 KB	Output isn't correct
5	Correct	1 ms	2652 KB	Output is correct
6	Incorrect	2 ms	2652 KB	Output isn't correct
7	Correct	3 ms	2652 KB	Output is correct
8	Incorrect	3 ms	2908 KB	Output isn't correct
9	Correct	5 ms	2908 KB	Output is correct
10	Correct	4 ms	2904 KB	Output is correct
11	Correct	8 ms	2904 KB	Output is correct
12	Incorrect	44 ms	3668 KB	Output isn't correct
13	Incorrect	91 ms	4952 KB	Output isn't correct
14	Correct	181 ms	5716 KB	Output is correct
15	Incorrect	434 ms	6480 KB	Output isn't correct
16	Incorrect	580 ms	6512 KB	Output isn't correct
17	Incorrect	433 ms	6480 KB	Output isn't correct
18	Correct	280 ms	6480 KB	Output is correct
19	Incorrect	581 ms	6484 KB	Output isn't correct
20	Incorrect	555 ms	6480 KB	Output isn't correct