#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
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 ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 4 |
Correct |
2 ms |
640 KB |
Output is correct |
| 5 |
Correct |
1 ms |
768 KB |
Output is correct |
| 6 |
Correct |
5 ms |
768 KB |
Output is correct |
| 7 |
Correct |
3 ms |
896 KB |
Output is correct |
| 8 |
Incorrect |
6 ms |
1024 KB |
Output isn't correct |
| 9 |
Correct |
5 ms |
1152 KB |
Output is correct |
| 10 |
Correct |
11 ms |
1280 KB |
Output is correct |
| 11 |
Correct |
7 ms |
1280 KB |
Output is correct |
| 12 |
Correct |
172 ms |
2048 KB |
Output is correct |
| 13 |
Incorrect |
266 ms |
2936 KB |
Output isn't correct |
| 14 |
Correct |
74 ms |
3712 KB |
Output is correct |
| 15 |
Execution timed out |
3057 ms |
4732 KB |
Time limit exceeded |
| 16 |
Execution timed out |
3058 ms |
4856 KB |
Time limit exceeded |
| 17 |
Execution timed out |
3069 ms |
4732 KB |
Time limit exceeded |
| 18 |
Correct |
104 ms |
4480 KB |
Output is correct |
| 19 |
Execution timed out |
3079 ms |
4984 KB |
Time limit exceeded |
| 20 |
Execution timed out |
3087 ms |
4984 KB |
Time limit exceeded |
