Submission #285247

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
285247	2020-08-28T13:33:32 Z	CaroLinda	Sailing Race (CEOI12_race)	C++14	100 / 100	1391 ms	4984 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 val[MAXN] ;
int dp[MAXN][MAXN][2] , dpLinha[MAXN][MAXN][2] ;
vector<int> adj[MAXN] ;
bool graph[MAXN][MAXN] ;

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) ;
            graph[i][x-1] = true ;
        }

    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 < N ; i++ )
        for(int j = 0 ; j < 2 ; j++ )
        {
            for(int g = 0 ; g < N ; g++  )val[g] = 0 ;

            for(int g = (i + t[j] + N)%N ; g != i ; (g += t[j] + N) %= N )
                for(int h = (g + t[j] + N) % N ; h != i ; h = (h + t[j]+N)%N )
                {

                    int best = max( dp[h][ (i+t[!j]+N)%N ][j] , dp[h][ (g + t[j] + N)%N ][!j]  ) ;
                    if(ans < best + val[h] + 2 && val[h] > 0 && graph[g][i] )
                    {
                        ans = best + val[h] + 2 ;
                        curId = g ;
                    }

                    if( graph[g][h] ) val[h] = max(val[h] , dpLinha[i][g][j] ) ;

                }
        }

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

}

Compilation message

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

Subtask #1

100.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	640 KB	Output is correct
4	Correct	2 ms	640 KB	Output is correct
5	Correct	1 ms	768 KB	Output is correct
6	Correct	4 ms	896 KB	Output is correct
7	Correct	4 ms	896 KB	Output is correct
8	Correct	6 ms	1024 KB	Output is correct
9	Correct	5 ms	1152 KB	Output is correct
10	Correct	14 ms	1408 KB	Output is correct
11	Correct	7 ms	1152 KB	Output is correct
12	Correct	88 ms	2112 KB	Output is correct
13	Correct	228 ms	2944 KB	Output is correct
14	Correct	81 ms	3840 KB	Output is correct
15	Correct	1328 ms	4856 KB	Output is correct
16	Correct	1246 ms	4984 KB	Output is correct
17	Correct	1151 ms	4856 KB	Output is correct
18	Correct	113 ms	4732 KB	Output is correct
19	Correct	1391 ms	4984 KB	Output is correct
20	Correct	1351 ms	4864 KB	Output is correct