#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int k;
const int NMAX = 500;
int dp[NMAX + 5][NMAX + 5][2];
int forced[NMAX + 5][NMAX + 5][2];
int bst[NMAX + 5][NMAX + 5];
int graph[NMAX + 5][NMAX + 5];
bool is_in_strict(int st,int dr,int pos){
if(st <= dr){
return st < pos && pos < dr;
}
return st < pos || pos < dr;
}
int nxt(int pos,int d = 1){
return (pos + d - 1) % n + 1;
}
int ant(int pos){
return nxt(pos,n - 1);
}
int dist(int i,int j){
if(j >= i){
return j - i;
}
return i + n - j;
}
int main(){
scanf("%d %d",&n,&k);
for(int i = 1;i <= n;i++){
int u = i,v = -1;
while(scanf("%d",&v) == 1){
if(v == 0){
break;
}
graph[u][v] = 1;
}
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
dp[i][j][0] = 0;
dp[i][j][1] = 0;
forced[i][j][0] = -2 * n * (i != j);
forced[i][j][1] = -2 * n * (i != j);
}
}
for(int l = 1;l < n;l++){
for(int i = 1;i <= n;i++){
int j = nxt(i,l);
for(int k = nxt(i);k != j;k = nxt(k)){
if(graph[i][k]){
dp[i][j][0] = max(dp[i][j][0],1 + max(dp[i][k][1],dp[k][j][0]));
forced[i][j][0] = max(forced[i][j][0],1 + forced[k][j][0]);
}
}
if(graph[i][j]){
forced[i][j][0] = max(forced[i][j][0],1);
}
for(int k = ant(j);k != i;k = ant(k)){
if(graph[j][k]){
dp[i][j][1] = max(dp[i][j][1],1 + max(dp[k][j][0],dp[i][k][1]));
forced[i][j][1] = max(forced[i][j][1],1 + forced[i][k][1]);
}
}
if(graph[j][i]){
forced[i][j][1] = max(forced[i][j][1],1);
}
}
}
int ans = 0;
int fst = -1;
for(int i = 1;i <= n;i++){
for(int k = nxt(i);k != i;k = nxt(k)){
if(graph[i][k] == 1){
int a = dp[i][k][1];
int b = dp[k][i][0];
if(ans < 1 + max(a,b)){
ans = 1 + max(a,b);
fst = i;
}
}
}
}
if(k){
for(int j = 1;j <= n;j++){
for(int k = nxt(j);k != j;k = nxt(k)){
int bst_int = -1,bst_ext = -1;
for(int i = ant(k);i != j;i = ant(i)){
if(graph[i][j]){
bst_int = i;
break;
}
}
for(int i = nxt(k);i != j;i = nxt(i)){
if(graph[i][j]){
bst_ext = i;
break;
}
}
///interior
int i = bst_int;
for(int l = nxt(j);l != k;l = nxt(l)){
if(graph[k][l] && i != -1 && is_in_strict(l,k,i)){
if(ans < 2 + forced[k][j][1] + max(dp[j][l][1],dp[l][i][0])){
ans = 2 + forced[k][j][1] + max(dp[j][l][1],dp[l][i][0]);
fst = i;
}
}
}
///exterior
i = bst_ext;
for(int l = nxt(k);l != j;l = nxt(l)){
if(graph[k][l] && i != -1 && is_in_strict(k,l,i)){
if(ans < 2 + forced[j][k][0] + max(dp[l][j][0],dp[i][l][1])){
ans = 2 + forced[j][k][0] + max(dp[l][j][0],dp[i][l][1]);
fst = i;
}
}
}
}
}
}
printf("%d\n%d\n",ans,fst);
return 0;
}
Compilation message
race.cpp: In function 'int main()':
race.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&k);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
768 KB |
Output is correct |
| 5 |
Correct |
2 ms |
768 KB |
Output is correct |
| 6 |
Correct |
5 ms |
896 KB |
Output is correct |
| 7 |
Correct |
5 ms |
1056 KB |
Output is correct |
| 8 |
Correct |
9 ms |
1152 KB |
Output is correct |
| 9 |
Correct |
8 ms |
1152 KB |
Output is correct |
| 10 |
Correct |
8 ms |
1280 KB |
Output is correct |
| 11 |
Correct |
11 ms |
1280 KB |
Output is correct |
| 12 |
Correct |
129 ms |
2424 KB |
Output is correct |
| 13 |
Correct |
375 ms |
3328 KB |
Output is correct |
| 14 |
Correct |
401 ms |
4344 KB |
Output is correct |
| 15 |
Correct |
1816 ms |
5368 KB |
Output is correct |
| 16 |
Correct |
1922 ms |
5344 KB |
Output is correct |
| 17 |
Correct |
1812 ms |
5300 KB |
Output is correct |
| 18 |
Correct |
770 ms |
5248 KB |
Output is correct |
| 19 |
Correct |
2103 ms |
5248 KB |
Output is correct |
| 20 |
Correct |
2033 ms |
5304 KB |
Output is correct |
