oj.uz

Submission #55219

# Submission time Handle Problem Language Result Execution time Memory
55219 2018-07-06T11:55:16 Z dfistric Sailing Race (CEOI12_race) C++14
40 / 100
 481 ms 2940 KB 
#include <bits/stdc++.h>

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)

using namespace std;

const int MAXN = 510;
vector <int> ve[MAXN];
int num_ways[MAXN][MAXN][2];

bool inside(int x, int y, int z, int t) {
  if (t == 0) swap(x, y);
  if (x < y) {
    return ((z > x) && (z < y));
  }
  return ((z > x) || (z < y));
}

int rek(int x, int y, int t) {
  int& out = num_ways[x][y][t];
  if (out != -1) return out;

  out = 0;
  for (int z : ve[y]) {
    if (!inside(x, y, z, t)) continue;
    //cout << x + 1 << " " << y + 1 << " " << t << " -> " << z + 1 << endl;
    out = max(out, 1 + max(rek(y, z, 1 - t), rek(x, z, t)));
  }
  //cout << x + 1 << " " << y + 1 << " " << t << " --- " << out << endl;
  return out;
}

int main() {
  ios_base::sync_with_stdio(false);
  memset(num_ways, -1, sizeof num_ways);

  int n, k;
  cin >> n >> k;
  REP(i, n) {
    int x;
    cin >> x;
    while (x) {
      ve[i].push_back(x - 1);
      //cout << i << " " << x - 1 << endl;
      cin >> x;
    }
  }

  int out = 0, st = 0;
  REP(i, n) {
    for (int j : ve[i]) {
      int tr = 1 + max(rek(i, j, 1), rek(i, j, 0));
      if (tr > out) {
        out = tr;
        st = i + 1;
      }
      //cout << i + 1 << " " << j + 1 << ": " << rek(i, j, 0) << " " << rek(i, j, 1) << endl;
    }
  }
cout << out << "\n" << st << "\n";

  return 0;
}

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2424 KB Output is correct
2 Incorrect 3 ms 2508 KB Output isn't correct
3 Incorrect 3 ms 2508 KB Output isn't correct
4 Incorrect 4 ms 2508 KB Output isn't correct
5 Correct 4 ms 2572 KB Output is correct
6 Incorrect 5 ms 2572 KB Output isn't correct
7 Correct 8 ms 2644 KB Output is correct
8 Incorrect 5 ms 2644 KB Output isn't correct
9 Correct 8 ms 2644 KB Output is correct
10 Correct 23 ms 2648 KB Output is correct
11 Correct 16 ms 2648 KB Output is correct
12 Incorrect 30 ms 2824 KB Output isn't correct
13 Incorrect 49 ms 2824 KB Output isn't correct
14 Correct 105 ms 2824 KB Output is correct
15 Incorrect 252 ms 2900 KB Output isn't correct
16 Incorrect 347 ms 2900 KB Output isn't correct
17 Incorrect 263 ms 2900 KB Output isn't correct
18 Correct 105 ms 2900 KB Output is correct
19 Incorrect 394 ms 2908 KB Output isn't correct
20 Incorrect 481 ms 2940 KB Output isn't correct