oj.uz

답안 #1017269

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1017269 2024-07-09T07:06:21 Z MMihalev Sailing Race (CEOI12_race) C++14
85 / 100
 1396 ms 6904 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 curer=0;
                    int S=-1;
                    int sz=0;
                    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+curer+1+dist[T][X][dir];
                            if(curr>ans)
                            {
                                ans=curr;
                                idx=S;
                            }
                        }
                        if(edge[X][T])
                        {
                            okST=1;
                            if(max(dp[Y][n-2-i][dir],dp[Y][sz][1-dir])>curer)
                            {
                                curer=max(dp[Y][n-2-i][dir],dp[Y][sz][1-dir]);
                                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=-1;
                    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+dp[Y][suf][dir];
                            if(cur>ans)
                            {
                                ans=cur;
                                idx=S;
                            }
                        }
                        if(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;
}

Subtask #1
85.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Incorrect 1 ms 2652 KB Output isn't correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 3 ms 2908 KB Output is correct
7 Correct 3 ms 2908 KB Output is correct
8 Correct 5 ms 4700 KB Output is correct
9 Correct 5 ms 4700 KB Output is correct
10 Correct 7 ms 4700 KB Output is correct
11 Correct 7 ms 3160 KB Output is correct
12 Correct 78 ms 3932 KB Output is correct
13 Correct 187 ms 5980 KB Output is correct
14 Correct 184 ms 6232 KB Output is correct
15 Incorrect 1010 ms 6904 KB Output isn't correct
16 Incorrect 1200 ms 6768 KB Output isn't correct
17 Correct 978 ms 6736 KB Output is correct
18 Correct 305 ms 6740 KB Output is correct
19 Correct 1337 ms 6552 KB Output is correct
20 Correct 1396 ms 6740 KB Output is correct