#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int len = 503;
int dp[len][len][2], mat[len][len], adis[len][len], cdis[len][len];
vector<int> adj[len];
bool ins(int a, int b, int c){
return ((a < c && c < b) || (a > b && (a < c || c < b)));
}
int main(){
int n, tp;
scanf("%d %d", &n, &tp);
for (int i = 0; i < n; i++){
while (true){
int temp;
scanf("%d", &temp);
if (!temp)
break;
adj[i].pb(temp-1);
mat[i][temp-1] = 1;
}
}
int ans = 0, st = 0;
for (int sz = 1; sz <= n-1; sz++){
for (int a = 0; a < n; a++){
int b = (a+sz)%n;
/*if ((n+b-a)%n > n/2){
dp[a][b][0] = dp[b][a][1];
dp[a][b][1] = dp[b][a][0];
continue;
}*/
for (int j = 0; j < adj[a].size(); j++){
int v = adj[a][j];
if (ins(a, b, v))
dp[a][b][0] = max(dp[a][b][0], max(dp[a][v][1], dp[v][b][0])+1);
}
for (int j = 0; j < adj[b].size(); j++){
int v = adj[b][j];
if (ins(a, b, v))
dp[a][b][1] = max(dp[a][b][1], max(dp[a][v][1], dp[v][b][0])+1);
}
if (mat[b][a] && dp[a][b][0]+1 > ans)
ans = dp[a][b][0]+1, st = b;
if (mat[a][b] && dp[a][b][1]+1 > ans)
ans = dp[a][b][1]+1, st = a;
}
}
//printf("ans = %d, st = %d\n", ans, st);
if (tp == 0 || ans == n-1){
printf("%d\n%d\n", ans, st+1);
return 0;
}
for (int sz = 1; sz <= n-1; sz++){
for (int a = 0; a < n; a++){
int b = (a+sz)%n;
if (mat[a][b])
adis[a][b] = 1;
for (int j = 0; j < adj[a].size(); j++){
int v = adj[a][j];
if (ins(a, b, v) && adis[v][b])
adis[a][b] = max(adis[a][b], adis[v][b]+1);
}
b = (a+n-sz)%n;
if (mat[a][b])
cdis[a][b] = 1;
for (int j = 0; j < adj[a].size(); j++){
int v = adj[a][j];
if (ins(b, a, v) && cdis[v][b])
cdis[a][b] = max(cdis[a][b], cdis[v][b]+1);
}
}
}
for (int b = 0; b < n; b++){
for (int c = 0; c < n; c++){
if (c == b || adis[b][c] == 0)
continue;
int a = -1;
for (int j = (c+1)%n; j != b; j = (j+1)%n){
if (mat[j][b]){
a = j;
break;
}
}
if (a == -1)
continue;
for (int j = 0; j < adj[c].size(); j++){
int v = adj[c][j];
if (ins(a, b, v) && adis[b][c]+max(dp[a][v][1], dp[v][b][0])+2 > ans)
ans = adis[b][c]+max(dp[a][v][1], dp[v][b][0])+2, st = a;
//printf("a = %d, b = %d, c = %d, v = %d, ans = %d\n", a+1, b+1, c+1, v+1, adis[b][c]+max(dp[a][v][1], dp[v][b][0])+2);
}
}
}
for (int b = 0; b < n; b++){
for (int c = 0; c < n; c++){
if (c == b || cdis[b][c] == 0)
continue;
int a = -1;
for (int j = (c+n-1)%n; j != b; j = (j+n-1)%n){
if (mat[j][b]){
a = j;
break;
}
}
if (a == -1)
continue;
for (int j = 0; j < adj[c].size(); j++){
int v = adj[c][j];
if (ins(b, a, v) && cdis[b][c]+max(dp[b][v][1], dp[v][a][0])+2 > ans)
ans = cdis[b][c]+max(dp[b][v][1], dp[v][a][0])+2, st = a;
//printf("a = %d, b = %d, c = %d, v = %d, ans = %d\n", a+1, b+1, c+1, v+1, cdis[b][c]+max(dp[b][v][1], dp[v][a][0])+2);
}
}
}
printf("%d\n%d\n", ans, st+1);
return 0;
}
/*
7 1 5
5 0 2
5 0
7 0
3 0
4 0
4 3 0
2 1 0
*/
Compilation message
race.cpp: In function 'int main()':
race.cpp:40:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < adj[a].size(); j++){
~~^~~~~~~~~~~~~~~
race.cpp:46:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < adj[b].size(); j++){
~~^~~~~~~~~~~~~~~
race.cpp:70:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < adj[a].size(); j++){
~~^~~~~~~~~~~~~~~
race.cpp:79:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < adj[a].size(); j++){
~~^~~~~~~~~~~~~~~
race.cpp:103:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < adj[c].size(); j++){
~~^~~~~~~~~~~~~~~
race.cpp:128:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < adj[c].size(); j++){
~~^~~~~~~~~~~~~~~
race.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &tp);
~~~~~^~~~~~~~~~~~~~~~~~
race.cpp:19:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &temp);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
512 KB |
Output is correct |
| 3 |
Correct |
3 ms |
640 KB |
Output is correct |
| 4 |
Correct |
3 ms |
768 KB |
Output is correct |
| 5 |
Correct |
2 ms |
640 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1024 KB |
Output is correct |
| 7 |
Correct |
4 ms |
768 KB |
Output is correct |
| 8 |
Correct |
5 ms |
1152 KB |
Output is correct |
| 9 |
Correct |
5 ms |
1024 KB |
Output is correct |
| 10 |
Correct |
9 ms |
1024 KB |
Output is correct |
| 11 |
Correct |
6 ms |
896 KB |
Output is correct |
| 12 |
Correct |
42 ms |
2304 KB |
Output is correct |
| 13 |
Correct |
148 ms |
3424 KB |
Output is correct |
| 14 |
Correct |
44 ms |
2816 KB |
Output is correct |
| 15 |
Correct |
402 ms |
5624 KB |
Output is correct |
| 16 |
Correct |
556 ms |
5624 KB |
Output is correct |
| 17 |
Correct |
396 ms |
5496 KB |
Output is correct |
| 18 |
Correct |
61 ms |
3456 KB |
Output is correct |
| 19 |
Correct |
551 ms |
5732 KB |
Output is correct |
| 20 |
Correct |
564 ms |
5752 KB |
Output is correct |
