oj.uz

답안 #1016637

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1016637 2024-07-08T09:35:54 Z MMihalev Sailing Race (CEOI12_race) C++14
50 / 100
 1437 ms 6684 KB 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N=5e2+3;
//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];
                    int dpedgeST=-1e9;
                    int S;
                    int sz=0;
                    for(int j=i-1;j>=0;j--)
                    {
                        int X=track[T][dir][j];
                        if(dist[T][X][dir]!=1e9 && edge[X][Y])
                        {
                            int cur=dpedgeST+1+dist[T][X][dir];
                            if(cur>ans)
                            {
                                ans=cur;
                                idx=S;
                            }
                        }
                        int cur=dp[Y][sz][1-dir]+(edge[X][T]==0 ? -1e9 : edge[X][T]);
                        if(cur>=0 && cur>dpedgeST)
                        {
                            dpedgeST=cur;
                            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;
                    for(int j=i-1;j>=0;j--)
                    {
                        int X=track[T][dir][j];
                        if(okST && 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
50.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Incorrect 3 ms 2652 KB Output isn't correct
7 Correct 3 ms 2652 KB Output is correct
8 Incorrect 5 ms 2912 KB Output isn't correct
9 Correct 5 ms 2744 KB Output is correct
10 Correct 5 ms 3020 KB Output is correct
11 Correct 8 ms 3020 KB Output is correct
12 Incorrect 80 ms 3744 KB Output isn't correct
13 Incorrect 192 ms 4836 KB Output isn't correct
14 Correct 195 ms 5712 KB Output is correct
15 Incorrect 1126 ms 6684 KB Output isn't correct
16 Incorrect 1310 ms 6500 KB Output isn't correct
17 Incorrect 1097 ms 6480 KB Output isn't correct
18 Correct 317 ms 6484 KB Output is correct
19 Incorrect 1420 ms 6680 KB Output isn't correct
20 Incorrect 1437 ms 6508 KB Output isn't correct