Submission #260099

#	Time	Username	Problem	Language	Result	Execution time	Memory
260099		MiricaMatei	Sailing Race (CEOI12_race)	C++14	40 / 100	537 ms	4856 KiB

race

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 505;

int n;
vector<int>G[MAXN];
int dp[MAXN][MAXN][3];
int mc[MAXN][MAXN];

int prv(int i) {
  i--;
  if (i == 0)
    i = n;
  return i;
}

int nxt(int i) {
  i++;
  if (i == n + 1)
    i = 1;
  return i;
}

int solve(int x, int y, int t) {
  if (dp[x][y][t] != -1)
    return dp[x][y][t];
  if (t == 0) {
    int mx = 0;
    for (int i = y; i != x; i = prv(i))
      if (mc[y][i])
        mx = max(mx, max(solve(x, i,  0), solve(y, i, 1)));
    dp[x][y][t] = 1 + mx;
  } else {
    int mx = 0;
    for (int i = y; i != x; i = nxt(i))
      if (mc[y][i])
        mx = max(mx, max(solve(y, i, 0), solve(x, i, 1)));
    dp[x][y][t] = 1 + mx;
  }
  return dp[x][y][t];
}

int main() {
  //freopen("date.in", "r", stdin);
  //freopen("date.out", "w", stdout);

  int k;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    while (x != 0) {
      G[i].push_back(x);
      mc[i][x] = 1;
      scanf("%d", &x);
    }
    for (int j = 1; j <= n; ++j)
      dp[i][j][0] = dp[i][j][1] = -1;
  }

  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      if (mc[i][j]) {
        dp[i][j][0] = solve(i, j, 0);
        dp[i][j][1] = solve(i, j, 1);
      }

  int ans = 0, w = 0;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      for (int t = 0; t <= 1; ++t)
        if (dp[i][j][t] > ans) {
          ans = dp[i][j][t];
          w = i;
        }

  printf("%d\n%d\n", ans, w);

  return 0;
}

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &k);
   ~~~~~^~~~~~~~~~~~~~~~
race.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &x);
     ~~~~~^~~~~~~~~~
race.cpp:57:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &x);
       ~~~~~^~~~~~~~~~

• Subtask 1: 40 / 100