#include<bits/stdc++.h>
using namespace std;
const int maxn = 500 + 5;
const int inf = 1e6;
int n,k;
int way[maxn][maxn];
vector<int> yaw[maxn];
int dp[maxn][maxn][2];
int dp2[maxn][maxn][2];
int mx[maxn];
int add(int x, int y) {
return ((x+y)%n + n)%n;
}
int f(int u, int v, int t) {
if(dp[u][v][t]==-1) {
dp[u][v][t] = 0;
int wow = (t==0 ? 1:-1);
for(int x=add(u,wow);x!=v;x=add(x,wow)) {
if(!way[u][x]) continue;
//if(u==4 && v==1) printf("%d %d %d -> %d\n",u,v,t,x);
dp[u][v][t] = max(dp[u][v][t], max(f(x,u,!t), f(x,v,t)) + 1);
}
}
return dp[u][v][t];
}
int g(int u, int v, int t) {
if(dp2[u][v][t]==-1) {
dp2[u][v][t] = -inf;
int wow = (t==0 ? 1:-1);
if(way[u][v]) dp2[u][v][t] = 1;
for(int x=add(u,wow);x!=v;x=add(x,wow)) {
if(!way[u][x]) continue;
// if(u==4 && v==2) printf("%d %d %d -> %d\n",u,v,t,x);
dp2[u][v][t] = max(dp2[u][v][t], g(x,v,t) + 1);
}
}
return dp2[u][v][t];
}
int main() {
scanf("%d%d",&n,&k);
for(int u=0;u<n;u++) {
int v;
while(scanf("%d",&v) && v) {
--v;
way[u][v] = 1;
yaw[v].push_back(u);
}
}
memset(dp,-1,sizeof(dp));
memset(dp2,-1,sizeof(dp2));
pair<int,int> res = {-1,-1};
for(int u=0;u<n;u++) res = max(res, {f(u,u,0), u});
if(k) {
for(int u=0;u<n;u++) {
//case 1
for(int v=0;v<n;v++) mx[v] = 0;
for(int v=add(u,1);v!=u;v=add(v,1)) {
if(way[u][v]) {
for(int x=add(v,1);x!=u;x=add(x,1)) {
// printf("case 1 : u = %d v = %d x = %d => 1 + %d + %d\n",u,v,x,mx[x],g(v,x,0));
res = max(res, {1 + mx[x] + g(v,x,0), u});
}
}
for(auto x : yaw[v]) mx[x] = max(mx[x], f(v,u,1) + 1);
}
//case 2
for(int v=0;v<n;v++) mx[v] = 0;
for(int v=add(u,-1);v!=u;v=add(v,-1)) {
if(way[u][v]) {
for(int x=add(v,-1);x!=u;x=add(x,-1)) {
// printf("case 2 : u = %d v = %d x = %d => 1 + %d + %d\n",u,v,x,mx[x],g(v,x,1));
res = max(res, {1 + mx[x] + g(v,x,1), u});
}
}
for(auto x : yaw[v]) mx[x] = max(mx[x], f(v,u,0) + 1);
}
}
for(int v=0;v<n;v++) {
//case 3
for(int u=0;u<n;u++) mx[u] = 0;
for(int u=add(v,-1);u!=v;u=add(u,-1)) {
if(way[u][v]) {
for(int x=add(v,1);x!=u;x=add(x,1)) {
// printf("case 2 : u = %d v = %d x = %d => 1 + %d + %d\n",u,v,x,mx[x],g(v,x,0));
res = max(res, {1 + mx[x] + g(v,x,0), u});
}
}
for(auto x : yaw[u]) mx[x] = max(mx[x], f(u,v,0) + 1);
}
//case 4
for(int u=0;u<n;u++) mx[u] = 0;
for(int u=add(v,1);u!=v;u=add(u,1)) {
if(way[u][v]) {
for(int x=add(v,-1);x!=u;x=add(x,-1)) {
// printf("case 2 : u = %d v = %d x = %d => 1 + %d + %d\n",u,v,x,mx[x],g(v,x,1));
res = max(res, {1 + mx[x] + g(v,x,1), u});
}
}
for(auto x : yaw[u]) mx[x] = max(mx[x], f(u,v,1) + 1);
}
}
}
printf("%d\n%d",res.first,res.second+1);
}
Compilation message
race.cpp: In function 'int main()':
race.cpp:42:7: 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 |
6 ms |
4312 KB |
Output is correct |
| 2 |
Correct |
7 ms |
4456 KB |
Output is correct |
| 3 |
Correct |
9 ms |
4664 KB |
Output is correct |
| 4 |
Correct |
10 ms |
4664 KB |
Output is correct |
| 5 |
Correct |
10 ms |
4672 KB |
Output is correct |
| 6 |
Correct |
21 ms |
4676 KB |
Output is correct |
| 7 |
Correct |
17 ms |
4724 KB |
Output is correct |
| 8 |
Correct |
38 ms |
4724 KB |
Output is correct |
| 9 |
Correct |
30 ms |
4772 KB |
Output is correct |
| 10 |
Correct |
37 ms |
4888 KB |
Output is correct |
| 11 |
Correct |
37 ms |
4896 KB |
Output is correct |
| 12 |
Correct |
547 ms |
5200 KB |
Output is correct |
| 13 |
Correct |
1490 ms |
5364 KB |
Output is correct |
| 14 |
Correct |
1238 ms |
5740 KB |
Output is correct |
| 15 |
Execution timed out |
3039 ms |
6136 KB |
Time limit exceeded |
| 16 |
Execution timed out |
3008 ms |
6316 KB |
Time limit exceeded |
| 17 |
Execution timed out |
3038 ms |
6324 KB |
Time limit exceeded |
| 18 |
Correct |
2143 ms |
6324 KB |
Output is correct |
| 19 |
Execution timed out |
3042 ms |
6600 KB |
Time limit exceeded |
| 20 |
Execution timed out |
3026 ms |
6764 KB |
Time limit exceeded |
