#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];
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;
int v=nxt[s];
for(int i2=1;i2<n;i2++,v=nxt[v]){
int pom=nxt[v],li=1;
while(pom!=s){
if(kr[s][v] and nw[pom]>0){
res=max(res,nw[pom]+dp2[nxt[v]][li-1][0]+2);
if(nw[pom]+dp2[nxt[v]][li-1][0]+2==res){
g=s;
}
}
pom=nxt[pom],li++;
}
for(int i3=1;i3<=n;i3++){
if(kr[i3][v]){
nw[i3]=max(nw[i3],dp[nxt[s]][i2-1][1]);
}
}
}
for(int i2=1;i2<=n;i2++) nw[i2]=-INFi;
v=s-1;
for(int i2=1;i2<n;i2++,v--){
if(v==0) v=n;
int pom=nxt[s],li=1;
while(pom!=v){
int odl=n-i2;
if(kr[s][v] and nw[pom]>0){
res=max(res,nw[pom]+dp2[pom][odl-li][1]+2);
if(nw[pom]+dp2[pom][odl-li][1]+2==res){
g=s;
}
}
pom=nxt[pom],li++;
}
for(int i3=1;i3<=n;i3++){
if(kr[i3][v]){
nw[i3]=max(nw[i3],dp[v][i2-1][0]);
}
}
}
}
for(int v=1;v<=n;v++){
for(int i2=1;i2<=n;i2++) nw[i2]=-INFi;
int s=nxt[v];
for(int i2=1;i2<n;i2++,s=nxt[s]){
int pom=nxt[s],li=1;
while(pom!=v){
int odl=n-i2;
if(kr[s][v] and nw[pom]>0){
res=max(res,nw[pom]+dp2[pom][odl-li][1]+2);
if(nw[pom]+dp2[pom][odl-li][1]+2==res){
g=s;
}
}
pom=nxt[pom],li++;
}
for(int i3=1;i3<=n;i3++){
if(kr[i3][s]){
nw[i3]=max(nw[i3],dp[nxt[v]][i2-1][1]);
}
}
}
s=v-1;
for(int i2=1;i2<=n;i2++) nw[i2]=-INFi;
for(int i2=1;i2<n;i2++,s--){
if(s==0) s=n;
int pom=nxt[v],li=0;
while(pom!=s){
if(kr[s][v] and nw[pom]>0){
res=max(res,nw[pom]+dp2[v][li][0]+2);
if(nw[pom]+dp2[v][li][0]+2==res){
g=s;
}
}
pom=nxt[pom],li++;
}
for(int i3=1;i3<=n;i3++){
if(kr[i3][s]){
nw[i3]=max(nw[i3],dp[s][i3-1][0]);
}
}
}
}
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 |
596 KB |
Output isn't correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Incorrect |
6 ms |
852 KB |
Output isn't correct |
| 7 |
Correct |
2 ms |
596 KB |
Output is correct |
| 8 |
Incorrect |
10 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 |
7 ms |
724 KB |
Output is correct |
| 12 |
Incorrect |
143 ms |
2032 KB |
Output isn't correct |
| 13 |
Incorrect |
381 ms |
2904 KB |
Output isn't correct |
| 14 |
Correct |
121 ms |
2252 KB |
Output is correct |
| 15 |
Incorrect |
2005 ms |
4672 KB |
Output isn't correct |
| 16 |
Incorrect |
2233 ms |
4712 KB |
Output isn't correct |
| 17 |
Incorrect |
2016 ms |
4720 KB |
Output isn't correct |
| 18 |
Correct |
196 ms |
2608 KB |
Output is correct |
| 19 |
Incorrect |
2456 ms |
4784 KB |
Output isn't correct |
| 20 |
Incorrect |
2466 ms |
4748 KB |
Output isn't correct |
