oj.uz

Submission #55218

# Submission time Handle Problem Language Result Execution time Memory
55218 2018-07-06T11:54:40 Z dfistric Sailing Race (CEOI12_race) C++14
40 / 100
 438 ms 2952 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 2296 KB Output is correct
2 Incorrect 4 ms 2404 KB Output isn't correct
3 Incorrect 4 ms 2480 KB Output isn't correct
4 Incorrect 4 ms 2516 KB Output isn't correct
5 Correct 5 ms 2532 KB Output is correct
6 Incorrect 5 ms 2592 KB Output isn't correct
7 Correct 8 ms 2608 KB Output is correct
8 Incorrect 6 ms 2608 KB Output isn't correct
9 Correct 11 ms 2608 KB Output is correct
10 Correct 19 ms 2700 KB Output is correct
11 Correct 13 ms 2700 KB Output is correct
12 Incorrect 26 ms 2736 KB Output isn't correct
13 Incorrect 43 ms 2736 KB Output isn't correct
14 Correct 69 ms 2736 KB Output is correct
15 Incorrect 231 ms 2736 KB Output isn't correct
16 Incorrect 292 ms 2864 KB Output isn't correct
17 Incorrect 223 ms 2864 KB Output isn't correct
18 Correct 111 ms 2864 KB Output is correct
19 Incorrect 415 ms 2864 KB Output isn't correct
20 Incorrect 438 ms 2952 KB Output isn't correct