Submission #982572

#TimeUsernameProblemLanguageResultExecution timeMemory
982572PanosPaskSailing Race (CEOI12_race)C++14
40 / 100
363 ms2644 KiB
#include <bits/stdc++.h> #define pb push_back #define MOD(var, M) (((var) >= (M)) ? ((var) - M) : (var)) using namespace std; const int MAXN = 500; int N, K; bool adj_list[MAXN][MAXN]; // dp[l][r][k]: Maximum number of stages if enclosed by l, r // and being in the stages such that l < s < r' // Where r' = l > r ? r = r + N : r // k == 0: Starting in l // k == 1: Starting in r int dp[MAXN][MAXN][2]; // first[l][r][k]: True iff the first path in dp[l][r][k] is (l, r) or (r, l) respectively // Before the intersection with the first stage // You can only choose one way to follow // Either from l to r or from r to l int bef[MAXN][MAXN][2]; // True if a stage can be organized from i to j bool stage(int i, int j) { return adj_list[i][j]; } int main(void) { scanf("%d %d", &N, &K); for (int i = 0; i < N; i++) { int v; scanf("%d", &v); while (v != 0) { v--; adj_list[i][v] = true; scanf("%d", &v); } } int ans = 0; int starting = 0; for (int len = 1; len <= N; len++) { for (int l = 0; l < N; l++) { int r_actual = l + len - 1; int r = MOD(r_actual, N); for (int i_actual = l + 1; i_actual < r_actual; i_actual++) { int i = MOD(i_actual, N); dp[l][r][0] = max(dp[l][r][0], dp[l][i][0]); dp[l][r][1] = max(dp[l][r][1], dp[i][r][1]); if (stage(l, i)) { dp[l][r][0] = max(dp[l][r][0], 1 + dp[i][r][0]); } if (stage(r, i)) { dp[l][r][1] = max(dp[l][r][1], 1 + dp[l][i][1]); } } if (stage(l, r)) { int res = 1 + dp[MOD(l + 1, N)][r][1]; if (res >= dp[l][r][0]) { // first[l][r][0] = true; dp[l][r][0] = res; } } if (stage(r, l)) { int res = 1 + dp[l][MOD(r_actual - 1, N)][0]; if (res >= dp[l][r][1]) { // first[l][r][1] = true; dp[l][r][1] = res; } } if (dp[l][r][0] > ans) { ans = dp[l][r][0]; starting = l; } if (dp[l][r][1] > ans) { ans = dp[l][r][1]; starting = r; } } } printf("%d\n%d\n", ans, starting + 1); return 0; }

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d %d", &N, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~
race.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         scanf("%d", &v);
      |         ~~~~~^~~~~~~~~~
race.cpp:45:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |             scanf("%d", &v);
      |             ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...