# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1018521 | MMihalev | Sailing Race (CEOI12_race) | C++14 | 1210 ms | 8100 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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++)
{
dp[u][used][dir]=dp[u][used-1][dir];
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;
}
}
}
}
}
}
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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |