#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
int dp1[512][1024],dp2[512][1024];
pair<int,int>ans;
vector<int>adj[512],rev[512];
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)x+=n; if(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)x+=n; if(j<x)continue;
dp2[i][j]=max(dp2[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<C&&C<B)break;
if(*x>B&&C<B)break;
if(*x<C&&B<*x)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(dp2[*x][D],dp1[D][B]),*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();
else x--;
if(*x>C&&C>B)break;
if(*x<B&&C>B)break;
if(*x>C&&B>*x)break;
for(auto D:adj[C]) if(*x<B){if(*x>D||D>B)
ans=max(ans,{dis[C]+2+max(dp1[D][*x+(D>*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:24:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
24 | if(i>x)x+=n; if(j<=x)continue;
| ^~
race.cpp:24:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
24 | if(i>x)x+=n; if(j<=x)continue;
| ^~
race.cpp:28:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
28 | if(i>=x)x+=n; if(j<x)continue;
| ^~
race.cpp:28:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
28 | if(i>=x)x+=n; if(j<x)continue;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
860 KB |
Output is correct |
| 6 |
Correct |
2 ms |
860 KB |
Output is correct |
| 7 |
Correct |
2 ms |
860 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1112 KB |
Output is correct |
| 10 |
Correct |
7 ms |
1372 KB |
Output is correct |
| 11 |
Correct |
5 ms |
1112 KB |
Output is correct |
| 12 |
Correct |
23 ms |
2140 KB |
Output is correct |
| 13 |
Correct |
41 ms |
2904 KB |
Output is correct |
| 14 |
Correct |
35 ms |
3672 KB |
Output is correct |
| 15 |
Correct |
233 ms |
4700 KB |
Output is correct |
| 16 |
Correct |
297 ms |
5040 KB |
Output is correct |
| 17 |
Correct |
223 ms |
4700 KB |
Output is correct |
| 18 |
Correct |
45 ms |
4444 KB |
Output is correct |
| 19 |
Correct |
354 ms |
4952 KB |
Output is correct |
| 20 |
Correct |
378 ms |
4952 KB |
Output is correct |
