Submission #1017266

#TimeUsernameProblemLanguageResultExecution timeMemory
1017266MMihalevSailing Race (CEOI12_race)C++14
95 / 100
1315 ms6992 KiB
#include<iostream> #include<vector> #include<algorithm> using namespace std; const int MAX_N=5e2+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++) { 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]; bool okST=0; int curer=0; int S=-1; int sz=0; for(int j=i-1;j>=0;j--) { int X=track[T][dir][j]; if(okST==1 && dist[T][X][dir]!=1e9 && edge[X][Y]) { int curr=1+curer+1+dist[T][X][dir]; if(curr>ans) { ans=curr; idx=S; } } if(edge[X][T]) { okST=1; if(max(dp[Y][n-2-i][dir],dp[Y][sz][1-dir])>curer) { curer=max(dp[Y][n-2-i][dir],dp[Y][sz][1-dir]); S=X; } 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=-1; for(int j=i-1;j>=0;j--) { int X=track[T][dir][j]; if(okST==1 && 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...