Submission #545129

#TimeUsernameProblemLanguageResultExecution timeMemory
545129rainboySailing Race (CEOI12_race)C11
100 / 100
1183 ms5328 KiB
#include <stdio.h> #include <string.h> #define N 500 #define add(x) (x + 1 == n ? 0 : x + 1) #define sub(x) (x == 0 ? n - 1 : x - 1) int max(int a, int b) { return a > b ? a : b; } int main() { static int aa[N][N], dp[N][N], dq[N][N], dr[N][N], ds[N][N], dt[N]; int n, t, i, i_, j, k, l, x_; scanf("%d%d", &n, &t); for (i = 0; i < n; i++) while (1) { scanf("%d", &j), j--; if (j == -1) break; aa[i][j] = 1; } for (i = 0; i < n; i++) { memset(dp[i], -1, n * sizeof *dp[i]); dp[i][i] = 0; j = i; do { int x = dp[i][j]; if (x != -1) for (k = add(j); k != i; k = add(k)) if (aa[j][k]) dp[i][k] = max(dp[i][k], x + 1); j = add(j); } while (j != i); memset(dq[i], -1, n * sizeof *dq[i]); dq[i][i] = 0; j = i; do { int x = dq[i][j]; if (x != -1) for (k = sub(j); k != i; k = sub(k)) if (aa[j][k]) dq[i][k] = max(dq[i][k], x + 1); j = sub(j); } while (j != i); } for (l = 1; l < n; l++) for (i = 0; i < n; i++) { int x; j = (i + l) % n; x = -1, k = add(i); while (1) { if (aa[i][k]) x = max(x, max(ds[add(i)][k], dr[j][k])); if (k == j) break; k = add(k); } dr[j][i] = x + 1; x = -1, k = sub(j); while (1) { if (aa[j][k]) x = max(x, max(dr[sub(j)][k], ds[i][k])); if (k == i) break; k = sub(k); } ds[i][j] = x + 1; } x_ = 0, i_ = 0; for (i = 0; i < n; i++) { int x = dr[(i - 1 + n) % n][i]; if (x_ < x) x_ = x, i_ = i; } if (t == 1) for (j = 0; j < n; j++) { memset(dt, -1, n * sizeof *dt); for (i = add(j); i != j; i = add(i)) { if (aa[i][j]) for (k = add(i); k != j; k = add(k)) if (dt[k] != -1) { int x = 1 + dt[k] + max(dr[sub(j)][k], ds[add(i)][k]); if (x_ < x) x_ = x, i_ = i; } if (dp[j][i] != -1) for (k = add(i); k != j; k = add(k)) if (aa[i][k]) dt[k] = max(dt[k], dp[j][i] + 1); } memset(dt, -1, n * sizeof *dt); for (i = sub(j); i != j; i = sub(i)) { if (aa[i][j]) for (k = sub(i); k != j; k = sub(k)) if (dt[k] != -1) { int x = 1 + dt[k] + max(ds[add(j)][k], dr[sub(i)][k]); if (x_ < x) x_ = x, i_ = i; } if (dq[j][i] != -1) for (k = sub(i); k != j; k = sub(k)) if (aa[i][k]) dt[k] = max(dt[k], dq[j][i] + 1); } } printf("%d\n", x_); printf("%d\n", i_ + 1); return 0; }

Compilation message (stderr)

race.c: In function 'main':
race.c:14:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  scanf("%d%d", &n, &t);
      |  ^~~~~~~~~~~~~~~~~~~~~
race.c:17:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |    scanf("%d", &j), j--;
      |    ^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...