#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[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][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=1;
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][i2-1][0]);
}
}
}
}
cout<<res<<" "<<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 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
2 ms |
596 KB |
Output is correct |
| 5 |
Correct |
1 ms |
460 KB |
Output is correct |
| 6 |
Correct |
6 ms |
864 KB |
Output is correct |
| 7 |
Correct |
3 ms |
652 KB |
Output is correct |
| 8 |
Correct |
10 ms |
976 KB |
Output is correct |
| 9 |
Correct |
5 ms |
756 KB |
Output is correct |
| 10 |
Correct |
4 ms |
724 KB |
Output is correct |
| 11 |
Correct |
6 ms |
724 KB |
Output is correct |
| 12 |
Correct |
146 ms |
2052 KB |
Output is correct |
| 13 |
Correct |
388 ms |
2904 KB |
Output is correct |
| 14 |
Correct |
114 ms |
2132 KB |
Output is correct |
| 15 |
Incorrect |
2028 ms |
4728 KB |
Output isn't correct |
| 16 |
Correct |
2271 ms |
4752 KB |
Output is correct |
| 17 |
Correct |
2033 ms |
4736 KB |
Output is correct |
| 18 |
Correct |
198 ms |
2612 KB |
Output is correct |
| 19 |
Correct |
2487 ms |
4756 KB |
Output is correct |
| 20 |
Correct |
2497 ms |
4728 KB |
Output is correct |
