#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef int ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll N=5e2+5;
const ll MOD=1e9+7;
const ll INF=(1<<28);
const ld pi=acos(-1);
#define REP(i,n) for(int i=0;i<n;++i)
#define REP1(i,n) for(int i=1;i<=n;++i)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
ll n,type,x,dp[N][N][2];
ll dis[N][N],rdis[N][N];
bitset<N> grid[N];
ll nxt_edge[N][N],lst_edge[N][N];
ll ansm,anss;
void upd(ll ans,ll id){
if(ans>=ansm){
ansm=ans,anss=id;
}
}
bool in(ll id,ll l,ll r){
if(r<l){
return (id<=r||id>=l);
}else{
return (l<=id&&id<=r);
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>type;
REP(i,n){
while(1){
cin>>x;
if(x==0)break;
grid[i][x-1]=1;
}
}
for(int len=2;len<n;len++){
for(int i=0,j=(i+len>=n?i+len-n:i+len);i<n;i++,j=(j+1>=n?0:j+1)){
for(int k=(i+1>=n?0:i+1);k!=j;k=(k+1>=n?0:k+1)){
//i,j,0 means boat is now at i
//i,j,1,means boat is now at j
dp[i][j][0]=max(dp[i][j][0],(grid[i][k]?1+max(dp[i][k][1],dp[k][j][0]):0));
dp[i][j][1]=max(dp[i][j][1],(grid[j][k]?1+max(dp[i][k][1],dp[k][j][0]):0));
}
}
}
//no cross
REP(i,n)REP(j,n){
if(i==j)continue;
if(grid[i][j])upd(max(dp[i][j][1],dp[j][i][0])+1,i);
}
if(type==0){cout<<ansm<<"\n"<<anss+1<<"\n";return 0;}
//
REP(i,N)REP(j,N)dis[i][j]=rdis[i][j]=-INF;
//type==1
for(int i=0;i<n;i++){
dis[i][i]=rdis[i][i]=0;
for(int j=i;;j=(j+1>=n?0:j+1)){
for(int k=0;k<n;k++){
if(grid[j][k]==0)continue;
if(in(k,i,j))continue;
dis[i][k]=max(dis[i][k],dis[i][j]+1);
}
if((j+1>=n?0:j+1)==i)break;
}
for(int j=i;;j=(j-1==-1?n-1:j-1)){
for(int k=0;k<n;k++){
if(grid[j][k]==0)continue;
if(in(k,j,i))continue;
rdis[i][k]=max(rdis[i][k],rdis[i][j]+1);
}
if((j-1==-1?n-1:j-1)==i)break;
}
/*
*/
}
REP(i,N)REP(j,N)nxt_edge[i][j]=lst_edge[i][j]=-1;
for(int i=0;i<n;i++){
for(int j=i;;j=(j-1==-1?n-1:j-1)){
nxt_edge[i][j]=nxt_edge[i][(j+1>=n?0:j+1)];
if(i==j)nxt_edge[i][j]=-1;
if(grid[j][i])nxt_edge[i][j]=j;
if((j-1==-1?n-1:j-1)==i)break;
}
for(int j=i;;j=(j+1>=n?0:j+1)){
lst_edge[i][j]=lst_edge[i][(j-1==-1?n-1:j-1)];
if(i==j)lst_edge[i][j]=-1;
if(grid[j][i])lst_edge[i][j]=j;
if((j+1>=n?0:j+1)==i)break;
}
}
for(ll b=0;b<n;b++){
for(ll c=0;c<n;c++){
if(b==c)continue;
ll a=nxt_edge[b][(c+1==n?0:c+1)];
for(ll d=0;d<n;d++){
if(d==a||d==b||d==c||a==-1||a==b||a==c)continue;
if(grid[c][d]&&in(d,a,b)){
ll val=1+dis[b][c]+1+max(dp[a][d][1],dp[d][b][0]);
upd(val,a);
}
}
a=lst_edge[b][(c-1==-1?n-1:c-1)];
for(ll d=0;d<n;d++){
if(d==a||d==b||d==c||a==-1||a==b||a==c)continue;
if(grid[c][d]&&in(d,b,a)){
ll val=1+rdis[b][c]+1+max(dp[b][d][1],dp[d][a][0]);
upd(val,a);
}
}
}
}
cout<<ansm<<"\n"<<anss+1<<"\n";
return 0;
}
/*
7 1
5 0
5 0
7 0
3 0
4 0
4 3 0
2 1 0
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4460 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4460 KB |
Output is correct |
| 4 |
Correct |
4 ms |
4460 KB |
Output is correct |
| 5 |
Correct |
1 ms |
492 KB |
Output is correct |
| 6 |
Correct |
7 ms |
4588 KB |
Output is correct |
| 7 |
Correct |
3 ms |
620 KB |
Output is correct |
| 8 |
Correct |
11 ms |
4588 KB |
Output is correct |
| 9 |
Correct |
5 ms |
748 KB |
Output is correct |
| 10 |
Correct |
4 ms |
876 KB |
Output is correct |
| 11 |
Correct |
8 ms |
748 KB |
Output is correct |
| 12 |
Correct |
139 ms |
5100 KB |
Output is correct |
| 13 |
Correct |
351 ms |
5488 KB |
Output is correct |
| 14 |
Correct |
147 ms |
1900 KB |
Output is correct |
| 15 |
Correct |
1782 ms |
6400 KB |
Output is correct |
| 16 |
Correct |
2065 ms |
6508 KB |
Output is correct |
| 17 |
Correct |
1837 ms |
6516 KB |
Output is correct |
| 18 |
Correct |
253 ms |
2540 KB |
Output is correct |
| 19 |
Correct |
2282 ms |
6456 KB |
Output is correct |
| 20 |
Correct |
2312 ms |
6456 KB |
Output is correct |
