#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define iii pair<int,ii>
#define vii vector<ii>
#define fi first
#define se second
#define endl '\n'
#define show(T) {for (auto x:T) cout<<x<<' ';cout<<endl;}
#define all(T) T.begin(),T.end()
using namespace std;
const double eps = 0.0000001;
const int mod = 1e9+7;
const int N = 505;
const int MATRIX_SIZE = 64;
const int BLOCK=500;
int n,dp1[N][N][2],dp2[N][N][2],k;
bool ke[N][N];
string trol;
vector <int> G[N];
int id(int x){
if (x>n) x-=n;
else if (x<1) x+=n;
return x;
}
void tim_dp1(){
for (int i=1,mid1,to1,mid2,to2;i<=n;++i){
for (int j=1;j<n;++j){
to1=id(i+j);
to2=id(i-j);
for (int z=1;z<j;++z){
mid1=id(i+z);
mid2=id(i-z);
if (ke[mid1][to1]&&dp1[i][mid1][0])
dp1[i][to1][0]=max(dp1[i][to1][0],dp1[i][mid1][0]+1);
if (ke[mid2][to2]&&dp1[i][mid2][1])
dp1[i][to2][1]=max(dp1[i][to2][1],dp1[i][mid2][1]+1);
}
}
}
}
void tim_dp2(){
for (int kc=1;kc<n;++kc){
for (int i=1,j1,j2,mid1,mid2;i<=n;++i){
j1=id(i+kc);
j2=id(i-kc);
dp2[i][j1][0]=max(dp1[i][j1][0],dp2[i][id(i+kc-1)][0]);
dp2[i][j2][1]=max(dp1[i][j2][1],dp2[i][id(i-kc+1)][1]);
for (int z=1;z<kc;++z){
mid1=id(i+z);
mid2=id(i-z);
if (dp1[i][mid1][0])
dp2[i][j1][0]=max(dp2[i][j1][0],dp1[i][mid1][0]+dp2[mid1][j1][0]);
if (dp1[i][mid2][1])
dp2[i][j2][1]=max(dp2[i][j2][1],dp1[i][mid2][1]+dp2[mid2][j2][1]);
}
if (ke[i][j1]) dp2[i][j1][0]=max(dp2[i][j1][0],dp2[j1][id(i+1)][1]+1);
if (ke[i][j2]) dp2[i][j2][1]=max(dp2[i][j2][1],dp2[j2][id(i-1)][0]+1);
}
}
}
void solve(){
cin>>n>>k;
cin.ignore();
for (int i=1,cur=0;i<=n;++i){
getline(cin,trol);
trol+=' ';
for (auto x:trol){
if (x==' '){
G[i].push_back(cur);
// cout<<i<<' '<<cur<<endl;
ke[i][cur]=true;
dp1[i][cur][0]=dp1[i][cur][1]=1;
cur=0;
}
else cur=cur*10+(x-'0');
}
}
tim_dp1();
tim_dp2();
int ans=0;
if (!k){
for (int i=1;i<=n;++i){
for (auto x:G[i]){
ans=max({ans,dp2[x][id(i-1)][0]+1,dp2[x][id(i+1)][1]+1});
}
}
cout<<ans;
return;
}
for (int i=1,mid;i<=n;++i){
for (int j=1;j<=n;++j){
if (dp1[j][i][0]){
mid=0;
for (int z=1,tam;z<n;++z){
tam=id(i+z);
if (tam==j) break;
if (ke[tam][j]) {
mid=tam;
break;
}
}
if (!mid) continue;
for (int z=1,tam;z<n;++z){
tam=id(mid+z);
if (tam==j) break;
if (!ke[i][tam]) continue;
ans=max(ans,max(dp2[tam][id(mid+1)][1],dp2[tam][id(j-1)][0])+dp1[j][i][0]+2);
}
}
if (dp1[j][i][1]){
mid=0;
for (int z=1,tam;z<n;++z){
tam=id(i-z);
if (tam==j) break;
if (ke[tam][j]){
mid=tam;
break;
}
}
if (!mid) continue;
for (int z=1,tam;z<n;++z){
tam=id(mid-z);
if (tam==j) break;
if (!ke[i][tam]) continue;
// if (j==5&&i==3) cout<<dp1[j][i][1]<<endl;
ans=max(ans,max(dp2[tam][id(mid-1)][0],dp2[tam][id(j+1)][1])+dp1[j][i][1]+2);
}
}
}
}
cout<<ans;
}
main() {
//freopen("ok.inp","r",stdin);
//freopen("ok.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
// cout<<endl<<clock()/1000.0;
}
Compilation message
race.cpp:134:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
134 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Unexpected end of file - int32 expected |
| 2 |
Incorrect |
1 ms |
6492 KB |
Unexpected end of file - int32 expected |
| 3 |
Incorrect |
1 ms |
6492 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
6492 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
3 ms |
6492 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
6492 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
3 ms |
6492 KB |
Unexpected end of file - int32 expected |
| 9 |
Incorrect |
5 ms |
6492 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
3 ms |
6748 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
7 ms |
6748 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
38 ms |
6744 KB |
Output isn't correct |
| 13 |
Incorrect |
118 ms |
7004 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
202 ms |
8272 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
521 ms |
9064 KB |
Unexpected end of file - int32 expected |
| 16 |
Incorrect |
558 ms |
9052 KB |
Unexpected end of file - int32 expected |
| 17 |
Incorrect |
528 ms |
9052 KB |
Unexpected end of file - int32 expected |
| 18 |
Incorrect |
394 ms |
8796 KB |
Unexpected end of file - int32 expected |
| 19 |
Incorrect |
599 ms |
9304 KB |
Unexpected end of file - int32 expected |
| 20 |
Incorrect |
592 ms |
9336 KB |
Unexpected end of file - int32 expected |
