#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];
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;
for (int i=1,tam;i<=n;++i){
cin>>tam;
while (tam){
// cout<<i<<' '<<tam<<endl;
G[i].push_back(tam);
ke[i][tam]=true;
dp1[i][tam][0]=dp1[i][tam][1]=1;
cin>>tam;
}
}
tim_dp1();
tim_dp2();
ii ans={0,0};
for (int i=1;i<=n;++i){
for (auto x:G[i]){
ans=max({ans,ii(dp2[x][id(i-1)][0]+1,i),ii(dp2[x][id(i+1)][1]+1,i)});
}
}
if (!k) {
cout<<ans.fi<<endl<<ans.se;
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)
for (int z=1,tam;z<n;++z){
tam=id(mid+z);
if (tam==j) break;
if (!ke[i][tam]) continue;
ans=max(ans,ii(max(dp2[tam][id(mid+1)][1],dp2[tam][id(j-1)][0])+dp1[j][i][0]+2,mid));
}
}
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;
ans=max(ans,ii(max(dp2[tam][id(mid-1)][0],dp2[tam][id(j+1)][1])+dp1[j][i][1]+2,mid));
}
}
}
}
cout<<ans.fi<<endl<<ans.se;
}
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:127:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
127 | main() {
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 7 |
Correct |
3 ms |
6488 KB |
Output is correct |
| 8 |
Correct |
3 ms |
6492 KB |
Output is correct |
| 9 |
Correct |
5 ms |
6492 KB |
Output is correct |
| 10 |
Correct |
4 ms |
6748 KB |
Output is correct |
| 11 |
Correct |
7 ms |
6492 KB |
Output is correct |
| 12 |
Correct |
40 ms |
6768 KB |
Output is correct |
| 13 |
Correct |
108 ms |
7004 KB |
Output is correct |
| 14 |
Correct |
236 ms |
7972 KB |
Output is correct |
| 15 |
Correct |
522 ms |
8796 KB |
Output is correct |
| 16 |
Correct |
593 ms |
9052 KB |
Output is correct |
| 17 |
Correct |
532 ms |
8796 KB |
Output is correct |
| 18 |
Correct |
399 ms |
8792 KB |
Output is correct |
| 19 |
Correct |
634 ms |
9160 KB |
Output is correct |
| 20 |
Correct |
612 ms |
9164 KB |
Output is correct |
