oj.uz

Submission #1018521

# Submission time Handle Problem Language Result Execution time Memory
1018521 2024-07-10T06:27:50 Z MMihalev Sailing Race (CEOI12_race) C++14
95 / 100
 1210 ms 8100 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++)
            {
                dp[u][used][dir]=dp[u][used-1][dir];
                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(max(dp[u][n-1][0],dp[u][n-1][1])>ans)
        {
            ans=dp[u][n-1][0];
            idx=u;
        }
    }
    int prevans=ans;
    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;
                        }
                    }
                }
            }
        }
    }
    if(n>=500)
    {
        //if(ans==prevans)while(1);
        //if(ans<=100)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;
}

Compilation message

race.cpp: In function 'void solve()':
race.cpp:123:9: warning: unused variable 'prevans' [-Wunused-variable]
  123 |     int prevans=ans;
      |         ^~~~~~~

Subtask #1
95.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 604 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 2908 KB Output is correct
6 Correct 3 ms 2908 KB Output is correct
7 Correct 4 ms 3128 KB Output is correct
8 Correct 5 ms 3164 KB Output is correct
9 Correct 6 ms 3280 KB Output is correct
10 Correct 5 ms 3164 KB Output is correct
11 Correct 9 ms 3308 KB Output is correct
12 Correct 68 ms 4196 KB Output is correct
13 Correct 193 ms 5504 KB Output is correct
14 Correct 240 ms 6352 KB Output is correct
15 Correct 1049 ms 7844 KB Output is correct
16 Incorrect 1129 ms 8100 KB Output isn't correct
17 Correct 959 ms 8100 KB Output is correct
18 Correct 413 ms 8016 KB Output is correct
19 Correct 1210 ms 8072 KB Output is correct
20 Correct 1187 ms 8020 KB Output is correct