#include<bits/stdc++.h>
using namespace std;
int dp1[1000][1000],dp2[1000][1000];
pair<int,int>ans;
vector<int>adj[501],rev[501];
int main(){
cin.tie(0)->sync_with_stdio(0);
int n,t;
cin>>n>>t;
for(int i=1;i<=n;i++){
int x;
cin>>x;
while(x){
adj[i].push_back(x);
rev[x].push_back(i);
cin>>x;
}
}
for(int d=2;d<=n;d++){
for(int i=1,j;i+d<=2*n;i++){
j=i+d;
for(auto x:adj[(i-1)%n+1]) {
if(i<=x+n&&x+n<=j)x+=n; if(x<i||j<=x)continue;
dp1[i][j]=max(dp1[i][j],1+max(dp1[x][j],dp2[i][x]));
}
for(auto x:adj[(j-1)%n+1]) {
if(i<=x+n&&x+n<=j)x+=n; if(x<=i||j<x)continue;
dp2[i][j]=max(dp1[i][j],1+max(dp1[x][j],dp2[i][x]));
}
}
}
for(int i=1;i<=n;i++)
ans=max(ans,{dp1[i][i+n],i});
if(t==0||ans.first>n-2){
cout<<ans.first<<'\n'<<ans.second<<'\n';
return 0;
}
for(int B=1;B<=n;B++){
if(rev[B].empty())continue;
vector<int>dis(n+1);
for(auto i:adj[B])dis[i]=1;
for(int C=B%n+1;C-B;C=C%n+1){
if(!dis[C]) continue;
for(auto j:adj[C])
dis[j]=max(dis[j],dis[C]+1);
auto x=upper_bound(rev[B].begin(),rev[B].end(),C);
if(x==rev[B].end()) {
x=rev[B].begin();
if(*x>B)continue;
}
if(*x>B&&C<B)break;
for(auto D:adj[C]) if(*x>B){if(*x<D||D<B)
ans=max(ans,{dis[C]+2+max(dp1[D+(D<B)*n][B+n],dp2[*x][D+(D<B)*n]),*x});
} else if(B>D&&D>*x)
ans=max(ans,{dis[C]+2+max(dp1[D][*x],dp2[B][D+n]),*x});
}
}
for(int B=1;B<=n;B++){
if(rev[B].empty())continue;
vector<int>dis(n+1);
for(auto i:adj[B])dis[i]=1;
for(int C=(B+n-2)%n+1;C-B;C=(C+n-2)%n+1){
if(!dis[C]) continue;
for(auto j:adj[C])
dis[j]=max(dis[j],dis[C]+1);
auto x=lower_bound(rev[B].begin(),rev[B].end(),C);
if(x==rev[B].begin()) {
x=--rev[B].end();
if(*x<B)continue;
} else x--;
if(*x<B&&C>B)break;
for(auto D:adj[C]) if(*x<B){if(*x>D||D>B)
ans=max(ans,{dis[C]+2+max(dp1[D+(D<*x)*n][*x+n],dp2[B][D+(D<*x)*n]),*x});
} else if(B<D&&D<*x)
ans=max(ans,{dis[C]+2+max(dp1[D][*x],dp2[B][D]),*x});
}
}
cout<<ans.first<<'\n'<<ans.second<<'\n';
}
Compilation message
race.cpp: In function 'int main()':
race.cpp:23:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
23 | if(i<=x+n&&x+n<=j)x+=n; if(x<i||j<=x)continue;
| ^~
race.cpp:23:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
23 | if(i<=x+n&&x+n<=j)x+=n; if(x<i||j<=x)continue;
| ^~
race.cpp:27:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
27 | if(i<=x+n&&x+n<=j)x+=n; if(x<=i||j<x)continue;
| ^~
race.cpp:27:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
27 | if(i<=x+n&&x+n<=j)x+=n; if(x<=i||j<x)continue;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
856 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 5 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
1372 KB |
Output isn't correct |
| 7 |
Incorrect |
3 ms |
1640 KB |
Output isn't correct |
| 8 |
Incorrect |
3 ms |
1624 KB |
Output isn't correct |
| 9 |
Incorrect |
4 ms |
1884 KB |
Output isn't correct |
| 10 |
Correct |
8 ms |
2140 KB |
Output is correct |
| 11 |
Incorrect |
5 ms |
2128 KB |
Output isn't correct |
| 12 |
Incorrect |
24 ms |
3692 KB |
Output isn't correct |
| 13 |
Incorrect |
46 ms |
5240 KB |
Output isn't correct |
| 14 |
Incorrect |
45 ms |
6744 KB |
Output isn't correct |
| 15 |
Incorrect |
245 ms |
8648 KB |
Output isn't correct |
| 16 |
Incorrect |
300 ms |
8792 KB |
Output isn't correct |
| 17 |
Incorrect |
243 ms |
8540 KB |
Output isn't correct |
| 18 |
Incorrect |
60 ms |
8336 KB |
Output isn't correct |
| 19 |
Incorrect |
364 ms |
9008 KB |
Output isn't correct |
| 20 |
Incorrect |
365 ms |
9000 KB |
Output isn't correct |
