#include<bits/stdc++.h>
using namespace std;
const int MN = 555;
int N, T;
int adj[MN][MN];
int cc1[MN][MN][2];
int dp1(int u, int v, int t) {
int &ret = cc1[u][v][t];
if(ret != -1) return ret;
ret = 0;
for(int i = (u + 1) % N; i != v; i = (i + 1) % N) {
if(adj[ (t? u : v) ][i]) {
ret = max(ret, dp1(u, i, 0) + 1);
ret = max(ret, dp1(i, v, 1) + 1);
}
}
return ret;
}
int cc2[MN][MN][2];
int dp2(int u, int v, int t) {
int &ret = cc2[u][v][t];
if(ret != -1) return ret;
if(u == v) return ret = 0;
ret = -1e9;
if(t) {
for(int i = (u + 1) % N;; i = (i + 1) % N) {
if(adj[u][i]) {
ret = max(ret, dp2(i, v, 1) + 1);
}
if(i == v) break;
}
}
else {
for(int i = (u + N - 1) % N;; i = (i + N - 1) % N) {
if(adj[u][i]) {
ret = max(ret, dp2(i, v, 0) + 1);
}
if(i == v) break;
}
}
return ret;
}
int main() {
scanf("%d %d", &N, &T);
for(int i = 0; i < N; i++) {
while(1) {
int t; scanf("%d", &t);
if(!t) break;
t--;
adj[i][t] = 1;
}
}
memset(cc1, -1, sizeof(cc1));
memset(cc2, -1, sizeof(cc2));
int ans = 0;
int p = -1;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) if(i != j) {
if(ans < dp1(i, j, 0) + 1) {
ans = dp1(i, j, 0) + 1;
p = i;
}
if(ans < dp1(j, i, 1) + 1) {
ans = dp1(j, i, 1) + 1;
p = i;
}
}
}
if(T) {
for(int i = 0; i < N; i++) {
vector<int> mx(N, -1e9);
for(int j = (i + 1) % N; j != i; j = (j + 1) % N) {
if(adj[i][j]) {
for(int k = (j + 1) % N; k != i; k = (k + 1) % N) {
if(ans < dp2(j, k, 1) + 2 + mx[k]) {
ans = dp2(j, k, 1) + 2 + mx[k];
p = i;
}
}
}
for(int k = (j + 1) % N; k != i; k = (k + 1) % N) {
if(adj[k][j]) {
mx[k] = max(mx[k], dp1(i, j, 0));
}
}
}
mx = vector<int>(N, -1e9);
for(int j = (i + N - 1) % N; j != i; j = (j + N - 1) % N) {
if(adj[i][j]) {
for(int k = (j + N - 1) % N; k != i; k = (k + N - 1) % N) {
if(ans < dp2(j, k, 0) + 2 + mx[k]) {
ans = dp2(j, k, 0) + 2 + mx[k];
p = i;
}
}
}
for(int k = (j + N - 1) % N; k != i; k = (k + N - 1) % N) {
if(adj[k][j]) {
mx[k] = max(mx[k], dp1(j, i, 1));
}
}
}
}
for(int i = 0; i < N; i++) {
vector<int> mx(N, -1e9);
for(int j = (i + N - 1) % N; j != i; j = (j + N - 1) % N) {
if(adj[j][i]) {
for(int k = (i + 1) % N; k != j; k = (k + 1) % N) {
if(ans < dp2(i, k, 1) + 2 + mx[k]) {
ans = dp2(i, k, 1) + 2 + mx[k];
p = j;
}
}
}
for(int k = (i + 1) % N; k != j; k = (k + 1) % N) {
if(adj[k][j]) {
mx[k] = max(mx[k], dp1(j, i, 1));
}
}
}
mx = vector<int>(N, -1e9);
for(int j = (i + 1) % N; j != i; j = (j + 1) % N) {
if(adj[j][i]) {
for(int k = (i + N - 1) % N; k != j; k = (k + N - 1) % N) {
if(ans < dp2(i, k, 0) + 2 + mx[k]) {
ans = dp2(i, k, 0) + 2 + mx[k];
p = j;
}
}
}
for(int k = (i + N - 1) % N; k != j; k = (k + N - 1) % N) {
if(adj[k][j]) {
mx[k] = max(mx[k], dp1(i, j, 0));
}
}
}
}
}
printf("%d\n%d", ans, p + 1);
}
Compilation message
race.cpp: In function 'int main()':
race.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &T);
~~~~~^~~~~~~~~~~~~~~~~
race.cpp:55:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int t; scanf("%d", &t);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5248 KB |
Output isn't correct |
| 2 |
Correct |
6 ms |
5248 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
5164 KB |
Output isn't correct |
| 4 |
Incorrect |
11 ms |
5248 KB |
Output isn't correct |
| 5 |
Incorrect |
9 ms |
5232 KB |
Output isn't correct |
| 6 |
Incorrect |
18 ms |
5248 KB |
Output isn't correct |
| 7 |
Correct |
14 ms |
5396 KB |
Output is correct |
| 8 |
Incorrect |
31 ms |
5376 KB |
Output isn't correct |
| 9 |
Correct |
21 ms |
5376 KB |
Output is correct |
| 10 |
Correct |
23 ms |
5444 KB |
Output is correct |
| 11 |
Correct |
23 ms |
5376 KB |
Output is correct |
| 12 |
Correct |
437 ms |
5632 KB |
Output is correct |
| 13 |
Incorrect |
1340 ms |
5868 KB |
Output isn't correct |
| 14 |
Incorrect |
740 ms |
6088 KB |
Output isn't correct |
| 15 |
Execution timed out |
3005 ms |
6380 KB |
Time limit exceeded |
| 16 |
Execution timed out |
3057 ms |
6416 KB |
Time limit exceeded |
| 17 |
Execution timed out |
3019 ms |
6376 KB |
Time limit exceeded |
| 18 |
Incorrect |
1472 ms |
6316 KB |
Output isn't correct |
| 19 |
Execution timed out |
3074 ms |
6444 KB |
Time limit exceeded |
| 20 |
Execution timed out |
3029 ms |
6444 KB |
Time limit exceeded |
