oj.uz

답안 #1018491

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1018491 2024-07-10T06:17:39 Z MMihalev Sailing Race (CEOI12_race) C++14
40 / 100
 1362 ms 8272 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++)
            {
                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 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;
                        }
                    }
                }
            }
        }

        //shit
        idx-=4;
        for(int dir=0;dir<2;dir++)
        {
            for(int T=1;T<=n;T++)
            {
                int idS;
                for(int i=0;i<n-1;i++)
                {
                    int Y=track[T][dir][i];
                    if(Y==idx)idS=i;
                }

                for(int i=idS+1;i<n-1;i++)
                {
                    int Y=track[T][dir][i];

                    for(int j=idS-1;j>=0;j--)
                    {
                        int X=track[T][dir][j];

                        if(dist[T][X][dir]!=1e9 && edge[X][Y] && edge[idx][T])
                        {
                            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;
                            }
                        }
                    }
                }
            }
        }
    }

    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:161:21: warning: 'idS' may be used uninitialized in this function [-Wmaybe-uninitialized]
  161 |                 int idS;
      |                     ^~~

Subtask #1
40.0 / 100.0

# 결과 실행 시간 메모리 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 2 ms 2908 KB Output isn't correct
5 Correct 2 ms 2908 KB Output is correct
6 Incorrect 3 ms 2908 KB Output isn't correct
7 Correct 3 ms 3120 KB Output is correct
8 Incorrect 5 ms 3164 KB Output isn't correct
9 Correct 6 ms 3164 KB Output is correct
10 Correct 5 ms 3164 KB Output is correct
11 Correct 8 ms 3164 KB Output is correct
12 Incorrect 74 ms 4016 KB Output isn't correct
13 Incorrect 187 ms 5460 KB Output isn't correct
14 Correct 198 ms 6360 KB Output is correct
15 Incorrect 1026 ms 8096 KB Output isn't correct
16 Incorrect 1204 ms 8092 KB Output isn't correct
17 Incorrect 1033 ms 8092 KB Output isn't correct
18 Correct 330 ms 8020 KB Output is correct
19 Incorrect 1331 ms 8016 KB Output isn't correct
20 Incorrect 1362 ms 8272 KB Output isn't correct