oj.uz

답안 #1017297

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1017297 2024-07-09T07:15:17 Z MMihalev Sailing Race (CEOI12_race) C++14
95 / 100
 1378 ms 6812 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;
                    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
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 1 ms 2652 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 4 ms 2908 KB Output is correct
7 Correct 4 ms 2908 KB Output is correct
8 Correct 5 ms 4700 KB Output is correct
9 Correct 7 ms 3164 KB Output is correct
10 Correct 7 ms 3164 KB Output is correct
11 Correct 9 ms 3164 KB Output is correct
12 Correct 85 ms 3916 KB Output is correct
13 Correct 194 ms 5000 KB Output is correct
14 Correct 212 ms 5840 KB Output is correct
15 Correct 1073 ms 6812 KB Output is correct
16 Incorrect 1070 ms 6740 KB Output isn't correct
17 Correct 901 ms 6736 KB Output is correct
18 Correct 294 ms 6736 KB Output is correct
19 Correct 1378 ms 6772 KB Output is correct
20 Correct 1337 ms 6736 KB Output is correct