#include<bits/stdc++.h>
using namespace std;
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>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)x+=n; if(j<=x)continue;
| ^~
race.cpp:23:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
23 | if(i>x)x+=n; if(j<=x)continue;
| ^~
race.cpp:27:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
27 | if(i>=x)x+=n; if(j<x)continue;
| ^~
race.cpp:27:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
27 | 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 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
604 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 |
3 ms |
860 KB |
Output isn't correct |
| 7 |
Correct |
2 ms |
856 KB |
Output is correct |
| 8 |
Incorrect |
3 ms |
1116 KB |
Output isn't correct |
| 9 |
Correct |
3 ms |
1116 KB |
Output is correct |
| 10 |
Correct |
8 ms |
1372 KB |
Output is correct |
| 11 |
Correct |
4 ms |
1116 KB |
Output is correct |
| 12 |
Incorrect |
22 ms |
2140 KB |
Output isn't correct |
| 13 |
Incorrect |
39 ms |
2904 KB |
Output isn't correct |
| 14 |
Correct |
33 ms |
3816 KB |
Output is correct |
| 15 |
Incorrect |
229 ms |
4808 KB |
Output isn't correct |
| 16 |
Incorrect |
291 ms |
4952 KB |
Output isn't correct |
| 17 |
Incorrect |
235 ms |
4812 KB |
Output isn't correct |
| 18 |
Correct |
46 ms |
4444 KB |
Output is correct |
| 19 |
Incorrect |
344 ms |
5056 KB |
Output isn't correct |
| 20 |
Incorrect |
348 ms |
5056 KB |
Output isn't correct |
