#include<bits/stdc++.h>
using namespace std;
int dp1[500][1000],dp2[500][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<=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-(x>n)*n][j-(x>n)*n],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-(x>n)*n][j-(x>n)*n],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][B+(D<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][*x],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 |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 5 |
Correct |
1 ms |
860 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
856 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
1136 KB |
Output isn't correct |
| 9 |
Incorrect |
3 ms |
1116 KB |
Output isn't correct |
| 10 |
Correct |
7 ms |
1432 KB |
Output is correct |
| 11 |
Incorrect |
3 ms |
1112 KB |
Output isn't correct |
| 12 |
Incorrect |
24 ms |
2332 KB |
Output isn't correct |
| 13 |
Incorrect |
37 ms |
2908 KB |
Output isn't correct |
| 14 |
Incorrect |
32 ms |
3672 KB |
Output isn't correct |
| 15 |
Runtime error |
101 ms |
9236 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
113 ms |
9688 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
97 ms |
9164 KB |
Execution killed with signal 11 |
| 18 |
Runtime error |
50 ms |
8788 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
150 ms |
9736 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
142 ms |
9728 KB |
Execution killed with signal 11 |
