Submission #260538

#TimeUsernameProblemLanguageResultExecution timeMemory
260538georgerapeanuSailing Race (CEOI12_race)C++11
5 / 100
609 ms5120 KiB
#include <cstdio> #include <vector> #include <algorithm> using namespace std; int n; int k; const int NMAX = 500; int dp[NMAX + 5][NMAX + 5][2]; int force[NMAX + 5][NMAX + 5][2]; int bst[NMAX + 5][NMAX + 5]; vector<int> graph[NMAX + 5]; vector<int> graphT[NMAX + 5]; bool is_in(int st,int dr,int pos){ if(st <= dr){ return st < pos && pos < dr; } return st < pos || pos < dr; } int nxt(int pos,int d = 1){ return (pos + d - 1) % n + 1; } int ant(int pos){ return nxt(pos,n - 1); } int dist(int i,int j){ if(j >= i){ return j - i; } return i + n - j; } int main(){ scanf("%d %d",&n,&k); for(int i = 1;i <= n;i++){ int u = i,v = -1; while(scanf("%d",&v) == 1){ if(v == 0){ break; } graph[u].push_back(v); graphT[v].push_back(u); } } for(int i = 1;i <= n;i++){ for(int j = 1;j <= n;j++){ dp[i][j][0] = -2 * n * (i != j); dp[i][j][1] = -2 * n * (i != j); force[i][j][0] = -2 * n * (i != j); force[i][j][1] = -2 * n * (i != j); } } for(int l = 1;l < n;l++){ for(int i = 1;i <= n;i++){ int j = nxt(i,l); for(auto it:graph[i]){ if(is_in(i,j,it)){ dp[i][j][0] = max(dp[i][j][0],1 + max(dp[it][j][0],dp[nxt(i)][it][1])); force[i][j][0] = max(force[i][j][0],1 + force[it][j][0]); } } for(auto it:graph[j]){ if(is_in(i,j,it)){ dp[i][j][1] = max(dp[i][j][1],1 + max(dp[i][it][1],dp[it][ant(j)][0])); force[i][j][1] = max(force[i][j][1],1 + force[i][it][1]); } } } } int ans = 0; int fst = -1; for(int i = 1;i <= n;i++){ for(auto it:graph[i]){ int a = dp[nxt(i)][it][1]; int b = dp[it][ant(i)][0]; if(ans < 1 + max(a,b)){ ans = 1 + max(a,b); fst = i; } } } if(k){ for(int j = 1;j <= n;j++){ for(int k = nxt(j);k != j;k = nxt(k)){ int bst_ext = -1; int bst_int = -1; for(auto i:graphT[j]){ if(is_in(j,k,i) == false){ if(bst_ext == -1 || dist(k,i) < dist(k,bst_ext)){ bst_ext = i; } } else{ if(bst_int == -1 || dist(i,k) < dist(bst_int,k)){ bst_int = i; } } } for(auto l:graph[k]){ if(is_in(j,k,l) == false){ if(bst_ext != -1 && is_in(k,l,bst_ext)){ int a = dp[l][ant(j)][0]; int b = dp[nxt(bst_ext)][l][1]; if(ans < 2 + max(a,b) + force[j][k][0]){ ans = 2 + max(a,b) + force[j][k][0]; //printf("%d %d %d %d and %d %d %d\n",j,k,l,bst_ext,force[j][k][0],a,b); fst = bst_ext; } } } else{ if(bst_int != -1 && is_in(l,k,bst_int)){ int a = dp[nxt(j)][l][1]; int b = dp[l][ant(bst_int)][0]; if(ans < 2 + max(a,b) + force[k][j][1]){ ans = 2 + max(a,b) + force[k][j][1]; //printf("%d %d %d %d and %d %d %d\n",j,k,l,bst_int,force[k][j][1],a,b); fst = bst_int; } } } } } } } printf("%d\n%d\n",ans,fst); return 0; }

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...