#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N=6e2+10;
//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++)
{
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][prev][0]!=1e9)
{
dist[u][v][0]=min(dist[u][v][0],dist[u][prev][0]+1);
}
}
if(edge[u][v])dist[u][v][0]=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][prev][1]!=1e9)
{
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(max(dp[u][n-1][0],dp[u][n-1][1])>ans)
{
ans=dp[u][n-1][0];
idx=u;
}
}
int prevans=ans;
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 Y=track[T][dir][i];
int S=-10;
int idS=-1;
for(int j=i-1;j>=0;j--)
{
int X=track[T][dir][j];
if(S!=-10 && dist[T][X][dir]!=1e9 && edge[X][Y])
{
int currer=1+dist[T][X][dir]+1+max(dp[Y][n-2-i][dir],dp[Y][i-idS-1][1-dir]);
if(currer>ans)
{
ans=currer;
idx=S;
}
}
if(edge[X][T])
{
S=X;
idS=j;
}
}
}
}
}
//shit
/*idx+=3;
for(int dir=0;dir<2;dir++)
{
for(int T=1;T<=n;T++)
{
int idS;
for(int i=0;i<n-1;i++)
{
int Y=track[T][dir][i];
if(Y==idx)idS=i;
}
for(int i=idS+1;i<n-1;i++)
{
int Y=track[T][dir][i];
for(int j=idS-1;j>=0;j--)
{
int X=track[T][dir][j];
if(dist[T][X][dir]!=1e9 && edge[X][Y] && edge[idx][T])
{
int currer=1+dist[T][X][dir]+1+max(dp[Y][n-2-i][dir],dp[Y][i-idS-1][1-dir]);
if(currer>ans)
{
ans=currer;
}
}
}
}
}
}*/
}
if(n>=500)
{
//if(ans==prevans)while(1);
//if(ans<=100)while(1);
}
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;
}
Compilation message
race.cpp: In function 'void solve()':
race.cpp:122:9: warning: unused variable 'prevans' [-Wunused-variable]
122 | int prevans=ans;
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
2 ms |
2904 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 6 |
Correct |
3 ms |
3052 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2908 KB |
Output is correct |
| 8 |
Correct |
5 ms |
3164 KB |
Output is correct |
| 9 |
Correct |
6 ms |
3164 KB |
Output is correct |
| 10 |
Correct |
5 ms |
3144 KB |
Output is correct |
| 11 |
Correct |
8 ms |
3164 KB |
Output is correct |
| 12 |
Correct |
64 ms |
4184 KB |
Output is correct |
| 13 |
Correct |
168 ms |
5376 KB |
Output is correct |
| 14 |
Correct |
208 ms |
6228 KB |
Output is correct |
| 15 |
Correct |
927 ms |
8016 KB |
Output is correct |
| 16 |
Incorrect |
1089 ms |
8096 KB |
Output isn't correct |
| 17 |
Correct |
918 ms |
8096 KB |
Output is correct |
| 18 |
Correct |
342 ms |
8272 KB |
Output is correct |
| 19 |
Correct |
1224 ms |
7852 KB |
Output is correct |
| 20 |
Correct |
1176 ms |
8100 KB |
Output is correct |
