Submission #285224

#	Time	Username	Problem	Language	Result	Execution time	Memory
285224		CaroLinda	Sailing Race (CEOI12_race)	C++14	55 / 100	3087 ms	4984 KiB

race

#include <bits/stdc++.h>

#define sz(x) (int)x.size()
#define mkt make_tuple
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define eb push_back
#define ll long long
#define mk make_pair
#define pii pair<int,int>
#define debug printf
#define all(x) x.begin(),x.end()

const int MAXN = 510 ;

using namespace std ;

int N , K , ans, curId ;
int t[2] = {-1,1} ;
int dp[MAXN][MAXN][2] , dpLinha[MAXN][MAXN][2] ;
vector<int> adj[MAXN] ;
vector<pii> edge ;

bool isInside(int x, int L , int R , int type )
{

    if(type == -1) swap(L,R) ;

    if( L > R ) return (L <= x || x <= R ) ;
    return L <= x && x <= R ;

}

void solve()
{
    lp(i,0,N) dpLinha[i][i][0] = dpLinha[i][i][1] = 1 ;

    for(int diff = 1 ; diff < N ; diff++ )
        for(int i = 0 ; i < N ; i++ )
            for(int j = 0 ; j < 2 ; j++ )
            {
                int R = ( i + diff * t[j] + N ) % N ;
                int &ptr = dp[i][R][j] ;
                ptr = 0 ;

                for(int viz : adj[i] )
                {
                    if(!isInside(viz, i , R, t[j] ) ) continue ;

                    ptr = max(ptr, 1 + dp[viz][R][j] ) ;
                    ptr = max(ptr, 1 + dp[viz][ (i+t[j]+N)%N ][ !j ] ) ;

                    if( dpLinha[viz][R][j] ) dpLinha[i][R][j] = max( dpLinha[i][R][j] , 1 + dpLinha[viz][R][j] ) ;

                }

                if(ptr  > ans )
                {
                    ans = ptr ;
                    curId = i ;
                }
            }
    lp(i,0,N)
        lp(j,0,N)
            lp(g,0,2)
                if(dpLinha[i][j][g]) dpLinha[i][j][g]-- ;
}

int main()
{
    scanf("%d%d", &N , &K ) ;
    for(int i = 0 , x ; i < N ; i++ )
        while( scanf("%d", &x) && x != 0 )
        {
            adj[i].push_back(x-1) ;
            edge.push_back( mk( i , x-1 ) ) ;
        }

    solve() ;

    if(K == 0)
    {
        printf("%d %d\n" , ans, curId + 1 );
        return 0 ;
    }

   /* for(int i = 0 ; i < N ; i++ )
    {
        for(int j = 0 ; j < N ; j++ )
            for(int g = 0 ; g < 2 ; g++ )
            {
                printf("dp[%d][%d][%d] = %d\n", i , j , g , dp[i][j][g] ) ;
            }
    } */

    ans = curId = 0 ;

    for(int i = 0 ; i < sz(edge) ; i++ )
        for(int j = i+1 ; j < sz(edge) ; j++ )
        {
            int A = edge[i].ff, B = edge[i].ss ;
            int X = edge[j].ff, Y = edge[j].ss ;

            if( A == X || A == Y || B == X || B == Y ) continue ;
            if( isInside(X, A, B, 1) == isInside(Y, A, B, 1) ) continue ;

            int typeB = isInside(A, Y, B, 1) ? 0 : 1 ;
            int typeA = !typeB ;

            int valY = max( dp[Y][ (B+t[typeA]+N)%N ][typeB] , dp[Y][ (A+t[typeB]+N)%N ][typeA] ) ;
            int valX = dpLinha[B][X][typeB] ;

            //debug("Em %d %d %d %d, valx eh %d e valy eh %d com typeB = %d\n" , A , B , X , Y , valX , valY , typeB ) ;
           // debug("%d %d e %d %d\n", Y, (B+t[typeA]+N)%N, Y , (A+t[typeB]+N)%N ) ;

            if( ans < valY+valX+2 )
            {
                ans = valY+valX+2 ;
                curId = A ;
            }

        }

    printf("%d %d\n" , ans, curId + 1 ) ;

}

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |     scanf("%d%d", &N , &K ) ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 55 / 100