Submission #1017219

# Submission time Handle Problem Language Result Execution time Memory
1017219 2024-07-09T06:45:16 Z MMihalev Sailing Race (CEOI12_race) C++14
80 / 100
1781 ms 6740 KB
#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()
{
    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 X=track[T][dir][i];
                    for(int j=i+1;j<n-1;j++)
                    {
                        int S=track[T][dir][j];
                        for(int r=j+1;r<n-1;r++)
                        {
                            int Y=track[T][dir][r];

                            if(edge[S][T] && edge[X][Y] && dist[T][X][dir]!=1e9)
                            {
                                int pref=r-j-1;
                                int suf=n-2-r;
                                int cur=1+dist[T][X][dir]+1+max(dp[Y][suf][dir],dp[Y][pref][1-dir]);
                                if(cur>ans)
                                {
                                    ans=cur;
                                    idx=S;
                                }
                            }
                        }
                    }
                }
            }
        }*/
        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 dpedgeST=-1;
                    int S;
                    int sz=0;
                    for(int j=i-1;j>=0;j--)
                    {
                        int X=track[T][dir][j];
                        if(dpedgeST!=-1 && dist[T][X][dir]!=1e9 && edge[X][Y])
                        {
                            int curr=1+dpedgeST+1+dist[T][X][dir];
                            if(curr>ans)
                            {
                                ans=curr;
                                idx=S;
                            }
                        }
                        if(edge[X][T])
                        {
                            int cur=dp[Y][sz][1-dir];
                            if(cur>dpedgeST)
                            {
                                dpedgeST=cur;
                                S=X;
                            }
                        }
                        sz++;
                    }
                }
            }
        }
        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];
                    bool okST=0;
                    int S;
                    for(int j=i-1;j>=0;j--)
                    {
                        int X=track[T][dir][j];
                        if(okST && edge[X][Y] && dist[T][X][dir]!=1e9)
                        {
                            int suf=n-2-i;
                            int cur=1+dist[T][X][dir]+1+dp[Y][suf][dir];
                            if(cur>ans)
                            {
                                ans=cur;
                                idx=S;
                            }
                        }
                        if(okST==0 && edge[X][T])
                        {
                            okST=1;
                            S=X;
                        }
                    }
                }
            }
        }
    }

    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;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 4 ms 856 KB Output is correct
7 Correct 3 ms 1116 KB Output is correct
8 Correct 6 ms 1116 KB Output is correct
9 Correct 5 ms 1116 KB Output is correct
10 Correct 5 ms 1624 KB Output is correct
11 Correct 8 ms 1372 KB Output is correct
12 Correct 95 ms 2556 KB Output is correct
13 Correct 256 ms 3988 KB Output is correct
14 Correct 193 ms 5200 KB Output is correct
15 Incorrect 1239 ms 6668 KB Output isn't correct
16 Incorrect 1481 ms 6740 KB Output isn't correct
17 Correct 1242 ms 6484 KB Output is correct
18 Correct 330 ms 6420 KB Output is correct
19 Correct 1721 ms 6672 KB Output is correct
20 Incorrect 1781 ms 6676 KB Output isn't correct