Submission #285241

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
285241	2020-08-28T13:11:50 Z	CaroLinda	Sailing Race (CEOI12_race)	C++14	75 / 100	3000 ms	5112 KB

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 ;

}

int main()
{
    scanf("%d%d", &N , &K ) ;
    for(int i = 0 , x ; i < N ; i++ )
        while( scanf("%d", &x) && x != 0 )
        {
            if(x == i+1) continue ;
            adj[i].push_back(x-1) ;
            edge.push_back( mk( i , x-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] > 0 || viz == R )
                        dpLinha[i][R][j] = max( dpLinha[i][R][j] , 1 + dpLinha[viz][R][j] ) ;

                }

                if(ptr  > ans )
                {
                    ans = ptr ;
                    curId = i ;
                }
            }

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

    for(int i = 0 ; i < sz(edge) ; i++ )
        for(int j = 0 ; 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] ;

            if(valX == 0) continue ;

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

        }

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

}

Compilation message

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

Subtask #1

75.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	512 KB	Output is correct
3	Correct	1 ms	512 KB	Output is correct
4	Correct	2 ms	640 KB	Output is correct
5	Correct	1 ms	768 KB	Output is correct
6	Correct	8 ms	896 KB	Output is correct
7	Correct	4 ms	896 KB	Output is correct
8	Correct	10 ms	1024 KB	Output is correct
9	Correct	5 ms	1152 KB	Output is correct
10	Correct	12 ms	1408 KB	Output is correct
11	Correct	7 ms	1280 KB	Output is correct
12	Correct	380 ms	2128 KB	Output is correct
13	Correct	545 ms	2936 KB	Output is correct
14	Correct	74 ms	3756 KB	Output is correct
15	Execution timed out	3091 ms	4860 KB	Time limit exceeded
16	Execution timed out	3088 ms	5112 KB	Time limit exceeded
17	Execution timed out	3055 ms	4860 KB	Time limit exceeded
18	Correct	104 ms	4608 KB	Output is correct
19	Execution timed out	3093 ms	5112 KB	Time limit exceeded
20	Execution timed out	3092 ms	5112 KB	Time limit exceeded