Submission #260160

#	Time	Username	Problem	Language	Result	Execution time	Memory
260160		MiricaMatei	Sailing Race (CEOI12_race)	C++14	40 / 100	2110 ms	10644 KiB

race

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 505;

int n;
vector<int>G[MAXN];
int dp1[MAXN][MAXN][3];
int dp2[MAXN][MAXN][3];
int mc[MAXN][MAXN];
int first[MAXN][MAXN][3];

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 solve1(int x, int y, int t) {
  if (dp1[x][y][t] != -1)
    return dp1[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, 1 + max(solve1(x, i, 0), solve1(y, i, 1)));
    dp1[x][y][t] = mx;
  } else {
    int mx = 0;
    for (int i = y; i != x; i = nxt(i))
      if (mc[y][i])
        mx = max(mx, 1 + max(solve1(y, i, 0), solve1(x, i, 1)));
    dp1[x][y][t] = mx;
  }
  return dp1[x][y][t];
}

bool in(int i, int k, int l, int t) {
  if (t == 0) {
    if (k > l) {
      if (k > i && i > l)
        return 1;
      return 0;
    } else {
      if (l > i && i > k)
        return 0;
      return 1;
    }
  } else {
    if (k > l) {
      if (k > i && i > l)
        return 0;
      return 1;
    } else {
      if (l > i && i > k)
        return 1;
      return 0;
    }
  }
}

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

  int p;
  scanf("%d%d", &n, &p);
  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)
      for (int t = 0; t <= 1; ++t)
        dp1[i][j][t] = dp2[i][j][t] = -1;
  }

  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
      dp1[i][j][0] = solve1(i, j, 0);
      dp1[i][j][1] = solve1(i, j, 1);
    }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
      for (int t = 0; t <= 1; ++t) {
        if (mc[i][j]) {
          dp1[i][j][t] = max(dp1[i][j][t], 0);
          dp1[i][j][t]++;
        }
      }
    }

  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 (mc[i][j] && dp1[i][j][t] > ans) {
          ans = dp1[i][j][t];
          w = i;
        }

  if (p == 1) {
    for (int j = 1; j <= n; ++j) {
      for (int k = prv(j); k != j; k = prv(k)) {
        for (int i = prv(k); i != j; i = prv(i)) {
          if (mc[i][j]) {
            first[j][k][0] = i;
            break;
          }
        }
      }
      for (int k = nxt(j); k != j; k = nxt(k)) {
        for (int i = nxt(k); i != j; i = nxt(i)) {
          if (mc[i][j]) {
            first[j][k][1] = i;
            break;
          }
        }
      }
    }
    for (int i = 1; i <= n; ++i) {
      for (int j = nxt(i); j != i; j = nxt(j)) {
        if (mc[j][i])
          dp2[j][i][0] = 1;
        for (int k = prv(j); k != i; k = prv(k))
          if (mc[j][k])
            dp2[j][i][0] = max(dp2[j][i][0], dp2[k][i][0] + 1);
      }
      for (int j = prv(i); j != i; j = prv(j)) {
        if (mc[j][i])
          dp2[j][i][1] = 1;
        for (int k = nxt(j); k != i; k = nxt(k))
          if (mc[j][k])
            dp2[j][i][1] = max(dp2[j][i][1], dp2[k][i][1] + 1);
      }
    }
    for (int j = 1; j <= n; ++j) {
      for (int k = prv(j); k != j; k = prv(k)) {
        for (int l = nxt(j); l != j; l = nxt(l)) {
          if (mc[k][l]) {
            int i = first[j][k][0];
            if (i == 0 || in(i, k, l, 0) == in(j, k, l, 0))
              continue;
            int sol = 1 + dp2[j][k][0] + 1 + max(dp1[j][l][0] - mc[j][l], dp1[i][l][1] - mc[i][l]);
            if (sol > ans) {
              ans = sol;
              w = i;
            }
          }
        }
      }
      for (int k = nxt(j); k != j; k = nxt(k)) {
        for (int l = prv(j); l != j; l = prv(l)) {
          if (mc[k][l]) {
            int i = first[j][k][1];
            if (i == 0 || in(i, k, l, 1) == in(j, k, l, 0))
              continue;
            int sol = 1 + dp2[j][k][1] + 1 + max(dp1[j][l][1] - mc[j][l], dp1[i][l][0] - mc[i][l]);
            if (sol > ans) {
              ans = sol;
              w = i;
            }
          }
        }
      }
    }

  }

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

  return 0;
}

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &p);
   ~~~~~^~~~~~~~~~~~~~~~
race.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &x);
     ~~~~~^~~~~~~~~~
race.cpp:83: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