#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=5e2+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e16;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
int n,dp[N][N][2],nxt[N],dp2[N][N][2],nw[N],nn[N];
bool kr[N][N];
void solve(){
int xd;
cin>>n>>xd;
for(int a,i=1;i<=n;i++){
cin>>a;
while(a!=0){
if(a!=i) kr[i][a]=1;
cin>>a;
}
}
if(n==1){
cout<<0<<"\n"<<1<<"\n";
return;
}
for(int i=1;i<n;i++) nxt[i]=i+1;
nxt[n]=1;
for(int dl=1;dl<n;dl++){
for(int i=1;i<=n;i++){
int v=i,kon=i+dl;
if(kon>n) kon-=n;
for(int i2=0;i2<=dl;i2++,v=nxt[v]){
if(kr[i][v]){
dp[i][dl][0]=max({dp[i][dl][0],dp[v][dl-i2][0]+1,
dp[nxt[i]][i2-1][1]+1});
}
if(kr[kon][v]){
dp[i][dl][1]=max({dp[i][dl][1],dp[i][i2][1]+1,
dp[v][dl-i2-1][0]+1});
}
}
}
}
int res=0,g=0;
for(int i=1;i<=n;i++){
res=max(res,dp[i][n-1][0]);
if(dp[i][n-1][0]==res) g=i;
}
if(xd==0){
cout<<res<<"\n"<<g<<"\n";
}else{
for(int dl=1;dl<n;dl++){
for(int i=1;i<=n;i++){
int v=i,kon=i+dl;
if(kon>n) kon-=n;
dp2[i][dl][0]=-INFi;
dp2[i][dl][1]=-INFi;
for(int i2=0;i2<=dl;i2++,v=nxt[v]){
if(kr[i][v]){
dp2[i][dl][0]=max(dp2[i][dl][0],dp2[v][dl-i2][0]+1);
}
if(kr[kon][v]){
dp2[i][dl][1]=max(dp2[i][dl][1],dp2[i][i2][1]+1);
}
}
}
}
for(int s=1;s<=n;s++){
for(int i2=1;i2<=n;i2++) nw[i2]=INFi,nn[i2]=INFi;
int v=nxt[s];
for(int i2=1;i2<n;i2++,v=nxt[v]){
int pom=nxt[v],l=1;
while(pom!=s){
int cnt=dp2[v][l][0]+1,dod=0;
if(nw[pom]!=INFi) dod=dp[nxt[s]][nw[pom]-1][1]+1;
if(nn[pom]!=INFi){
int g=nn[pom];
int odl=v-g;
if(odl<0) odl=v+n-g;
dod=max(dod,dp[g][odl-1][0]+1);
}
if(kr[s][v]){
res=max(res,cnt+dod);
if(cnt+dod==res){
g=s;
}
}
pom=nxt[pom],l++;
}
for(int i3=1;i3<=n;i3++){
if(kr[i3][v]){
nw[i3]=(nw[i3]==INFi?i2:nw[i3]);
nn[i3]=v;
}
}
}
for(int i2=1;i2<=n;i2++) nw[i2]=INFi,nn[i2]=INFi;
v=s-1;
for(int i2=1;i2<n;i2++,v--){
if(v==0) v=n;
int pom=nxt[s],l=1;
while(pom!=v){
int cnt=dp2[pom][(n-i2)-l][1]+1,dod=0;
if(nw[pom]!=INFi){
int g=nw[pom];
int odl=s-g;
if(odl<0) odl=s+n-g;
dod=dp[g][odl-1][0]+1;
}
if(nn[pom]!=INFi){
int g=nn[pom];
int odl=g-v;
if(odl<0) odl=g+n-v;
dod=max(dod,dp[nxt[v]][odl-1][1]+1);
}
//if(s==2 and v==5 and pom==3) cout<<nw[3]<<"\n";
if(kr[s][v]){
res=max(res,cnt+dod);
if(cnt+dod==res){
g=s;
}
}
pom=nxt[pom],l++;
}
for(int i3=1;i3<=n;i3++){
if(kr[i3][v]){
nn[i3]=(nn[i3]==INFi?v:nn[i3]);
nw[i3]=v;
}
}
}
}
cout<<res<<"\n"<<g<<"\n";
}
}
int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
int tt=1;
while(tt--) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
580 KB |
Output isn't correct |
| 5 |
Correct |
1 ms |
456 KB |
Output is correct |
| 6 |
Correct |
4 ms |
852 KB |
Output is correct |
| 7 |
Correct |
2 ms |
596 KB |
Output is correct |
| 8 |
Incorrect |
8 ms |
980 KB |
Output isn't correct |
| 9 |
Correct |
5 ms |
724 KB |
Output is correct |
| 10 |
Correct |
4 ms |
724 KB |
Output is correct |
| 11 |
Correct |
6 ms |
724 KB |
Output is correct |
| 12 |
Correct |
111 ms |
2048 KB |
Output is correct |
| 13 |
Incorrect |
300 ms |
2900 KB |
Output isn't correct |
| 14 |
Correct |
104 ms |
2132 KB |
Output is correct |
| 15 |
Incorrect |
1502 ms |
4672 KB |
Output isn't correct |
| 16 |
Correct |
1661 ms |
4888 KB |
Output is correct |
| 17 |
Incorrect |
1514 ms |
4600 KB |
Output isn't correct |
| 18 |
Correct |
179 ms |
2516 KB |
Output is correct |
| 19 |
Correct |
1803 ms |
4784 KB |
Output is correct |
| 20 |
Correct |
1809 ms |
4820 KB |
Output is correct |
