oj.uz

Submission #260158

# Submission time Handle Problem Language Result Execution time Memory
260158 2020-08-09T12:08:53 Z MiricaMatei Sailing Race (CEOI12_race) C++14
40 / 100
 1962 ms 10640 KB 
#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 (l > i && i > k)
        return 1;
      return 0;
    } else {
      if (l > i && i > k)
        return 0;
      return 1;
    }
  } else {
    if (k > l) {
      if (l > i && i > k)
        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]) {
            if (j == 4 && k == 3 && l == 7)
              int ok = 1;
            int i = first[j][k][0];
            if (i == 0 || !in(i, 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))
              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

race.cpp: In function 'int main()':
race.cpp:154:19: warning: unused variable 'ok' [-Wunused-variable]
               int ok = 1;
                   ^~
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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 640 KB Output isn't correct
3 Incorrect 1 ms 768 KB Output isn't correct
4 Incorrect 2 ms 1024 KB Output isn't correct
5 Correct 2 ms 896 KB Output is correct
6 Incorrect 5 ms 1280 KB Output isn't correct
7 Correct 4 ms 1152 KB Output is correct
8 Incorrect 9 ms 1664 KB Output isn't correct
9 Correct 7 ms 1408 KB Output is correct
10 Correct 9 ms 1664 KB Output is correct
11 Correct 10 ms 1664 KB Output is correct
12 Incorrect 127 ms 4472 KB Output isn't correct
13 Incorrect 292 ms 6392 KB Output isn't correct
14 Correct 175 ms 6012 KB Output is correct
15 Incorrect 1502 ms 10488 KB Output isn't correct
16 Incorrect 1796 ms 10640 KB Output isn't correct
17 Incorrect 1525 ms 10516 KB Output isn't correct
18 Correct 291 ms 7416 KB Output is correct
19 Incorrect 1962 ms 10616 KB Output isn't correct
20 Incorrect 1957 ms 10616 KB Output isn't correct