oj.uz

답안 #1017299

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1017299 2024-07-09T07:16:59 Z MMihalev Sailing Race (CEOI12_race) C++17
95 / 100
 2045 ms 6996 KB 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N=5e2+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++)
    {
        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];
                    bool okST=0;
                    int S;
                    int idS;
                    for(int j=i-1;j>=0;j--)
                    {
                        int X=track[T][dir][j];
                        if(okST==1 && dist[T][X][dir]!=1e9 && edge[X][Y])
                        {
                            int curr=1+dist[T][X][dir]+1+max(dp[Y][n-2-i][dir],dp[Y][i-idS-1][1-dir]);
                            if(curr>ans)
                            {
                                ans=curr;
                                idx=S;
                            }
                        }
                        if(edge[X][T])
                        {
                            okST=1;
                            S=X;
                            idS=j;
                        }
                    }
                }
            }
        }
        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=-1;
                    int idS;
                    for(int j=i-1;j>=0;j--)
                    {
                        int X=track[T][dir][j];
                        if(okST==1 && edge[X][Y] && dist[T][X][dir]!=1e9)
                        {
                            int suf=n-2-i;
                            int cur=1+dist[T][X][dir]+1+max(dp[Y][i-idS-1][1-dir],dp[Y][suf][dir]);
                            if(cur>ans)
                            {
                                ans=cur;
                                idx=S;
                            }
                        }
                        if(edge[X][T])
                        {
                            okST=1;
                            S=X;
                            idS=j;
                        }
                    }
                }
            }
        }
    }
    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;
}

Subtask #1
95.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 5 ms 4804 KB Output is correct
7 Correct 3 ms 3068 KB Output is correct
8 Correct 7 ms 2908 KB Output is correct
9 Correct 5 ms 3200 KB Output is correct
10 Correct 5 ms 4700 KB Output is correct
11 Correct 7 ms 4700 KB Output is correct
12 Correct 121 ms 4180 KB Output is correct
13 Correct 280 ms 5960 KB Output is correct
14 Correct 190 ms 5720 KB Output is correct
15 Correct 1473 ms 6700 KB Output is correct
16 Incorrect 1712 ms 6808 KB Output isn't correct
17 Correct 1503 ms 6996 KB Output is correct
18 Correct 318 ms 6736 KB Output is correct
19 Correct 2045 ms 6768 KB Output is correct
20 Correct 2035 ms 6556 KB Output is correct