#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N=5e2+3;
//0 clockwise
//1 counterclockwise
vector<int>track[MAX_N][2];//0 - ; 1 +
int n;
bool edge[MAX_N][MAX_N];
int type;
int dp[MAX_N][MAX_N][2];
int dist[MAX_N][MAX_N][2];//0 - ; 1 +
void precompute()
{
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
track[i][0].push_back(j);
}
for(int j=1;j<i;j++)
{
track[i][0].push_back(j);
}
//0
for(int j=i-1;j>=1;j--)
{
track[i][1].push_back(j);
}
for(int j=n;j>i;j--)
{
track[i][1].push_back(j);
}
//1
}
///track
for(int u=1;u<=n;u++)
{
dist[u][u][0]=0;
for(int j=0;j<n-1;j++)
{
int v=track[u][0][j];
dist[u][v][0]=1e9;
for(int r=0;r<j;r++)
{
int prev=track[u][0][r];
if(edge[prev][v])
{
dist[u][v][0]=min(dist[u][v][0],dist[u][prev][0]+1);
}
}
if(edge[u][v])dist[u][v][0]=1;
}
//0
dist[u][u][1]=0;
for(int j=0;j<n-1;j++)
{
int v=track[u][1][j];
dist[u][v][1]=1e9;
for(int r=0;r<j;r++)
{
int prev=track[u][1][r];
if(edge[prev][v])
{
dist[u][v][1]=min(dist[u][v][1],dist[u][prev][1]+1);
}
}
if(edge[u][v])dist[u][v][1]=1;
}
//1
}
///dist
for(int used=1;used<n;used++)
{
for(int dir=0;dir<2;dir++)
{
for(int u=1;u<=n;u++)
{
for(int i=0;i<used;i++)
{
int v=track[u][dir][i];
int pref=i;
int suf=used-1-i;
if(edge[u][v])dp[u][used][dir]=max(dp[u][used][dir],max(dp[v][suf][dir],dp[v][pref][1-dir])+1);
}
}
}
}
///dp
}
void read()
{
cin>>n>>type;
for(int u=1;u<=n;u++)
{
int v;
cin>>v;
while(v!=0)
{
edge[u][v]=1;
cin>>v;
}
}
}
void solve()
{
int ans=0;
int idx=1;
for(int u=1;u<=n;u++)
{
if(dp[u][n-1][0]>ans)
{
ans=dp[u][n-1][0];
idx=u;
}
}
if(type==1)
{
/*for(int dir=0;dir<2;dir++)
{
for(int T=1;T<=n;T++)
{
for(int i=0;i<n-1;i++)
{
int X=track[T][dir][i];
for(int j=i+1;j<n-1;j++)
{
int S=track[T][dir][j];
for(int r=j+1;r<n-1;r++)
{
int Y=track[T][dir][r];
if(edge[S][T] && edge[X][Y] && dist[T][X][dir]!=1e9)
{
int pref=r-j-1;
int suf=n-2-r;
int cur=1+dist[T][X][dir]+1+max(dp[Y][suf][dir],dp[Y][pref][1-dir]);
if(cur>ans)
{
ans=cur;
idx=S;
}
}
}
}
}
}
}*/
for(int dir=0;dir<2;dir++)
{
for(int T=1;T<=n;T++)
{
for(int i=0;i<n-1;i++)
{
int Y=track[T][dir][i];
int dpedgeST=-1e9;
int S;
int sz=0;
for(int j=i-1;j>=0;j--)
{
int X=track[T][dir][j];
if(dist[T][X][dir]!=1e9 && edge[X][Y])
{
int cur=dpedgeST+1+dist[T][X][dir];
if(cur>ans)
{
ans=cur;
idx=S;
}
}
int cur=dp[Y][sz][1-dir]+(edge[X][T]==0 ? -1e9 : edge[X][T]);
if(cur>=0 && cur>dpedgeST)
{
dpedgeST=cur;
S=X;
}
sz++;
}
}
}
}
for(int dir=0;dir<2;dir++)
{
for(int T=1;T<=n;T++)
{
for(int i=0;i<n-1;i++)
{
int Y=track[T][dir][i];
bool okST=0;
int S;
for(int j=i-1;j>=0;j--)
{
int X=track[T][dir][j];
if(okST && edge[X][Y] && dist[T][X][dir]!=1e9)
{
int suf=n-2-i;
int cur=1+dist[T][X][dir]+1+dp[Y][suf][dir];
if(cur>ans)
{
ans=cur;
idx=S;
}
}
if(edge[X][T])
{
okST=1;
S=X;
}
}
}
}
}
}
cout<<ans<<"\n";
cout<<idx<<"\n";
}
int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
read();
precompute();
solve();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2652 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2712 KB |
Output is correct |
| 8 |
Correct |
7 ms |
2920 KB |
Output is correct |
| 9 |
Correct |
5 ms |
2904 KB |
Output is correct |
| 10 |
Correct |
5 ms |
2876 KB |
Output is correct |
| 11 |
Correct |
8 ms |
2908 KB |
Output is correct |
| 12 |
Correct |
116 ms |
3732 KB |
Output is correct |
| 13 |
Correct |
298 ms |
4988 KB |
Output is correct |
| 14 |
Correct |
218 ms |
5716 KB |
Output is correct |
| 15 |
Incorrect |
1655 ms |
6680 KB |
Output isn't correct |
| 16 |
Incorrect |
1878 ms |
6680 KB |
Output isn't correct |
| 17 |
Correct |
1651 ms |
6480 KB |
Output is correct |
| 18 |
Correct |
345 ms |
6632 KB |
Output is correct |
| 19 |
Correct |
2158 ms |
6680 KB |
Output is correct |
| 20 |
Incorrect |
2202 ms |
6680 KB |
Output isn't correct |
