Submission #64522

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
64522	2018-08-04T18:49:50 Z	dfistric	Sailing Race (CEOI12_race)	C++14	40 / 100	1912 ms	8128 KB

race

#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];
int max_ways[MAXN][MAXN][2];
int dp[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)) {
      out = max(out, 1 + max(rek(y, z, 1 - t), rek(x, z, t)));
    }
  }

  return out;
}

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

  out = 0;
  for (int z : ve[y]) {
    if (inside(x, y, z, t) || z == y) {
      out = max(out, 1 + dfs(z, y, t));
    }
  }

  return out;
}

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

  int n, k;
  cin >> n >> k;
  REP(i, n) {
    int x;
    cin >> x;
    while (x) {
      ve[i].push_back(x - 1);
      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;
      }
    }
  }

  if (!k) {
    cout << out << "\n" << st << "\n";
    return 0;
  }

  REP(a, n) {
    REP(b, n) {
      if (a == b) continue;
      int c = a + 1;
      while (c != b) {
        max_ways[a][b][0] = max(max_ways[a][b][0], rek(b, c, 0));
        max_ways[a][b][1] = max(max_ways[a][b][1], rek(a, c, 1));
        c = (c + 1) % n;
      }
    }
  }

  REP(i, n) dp[i][i][0] = dp[i][i][1] = 0;

  REP(a, n) {
    for (int b : ve[a]) {
      REP(c, n) {
        if (c == b || c == a) continue;
        int tr = 0;
      }
    }
  }
  


  return 0;
}

Compilation message

race.cpp: In function 'int main()':
race.cpp:100:13: warning: unused variable 'tr' [-Wunused-variable]
         int tr = 0;
             ^~

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	4472 KB	Output is correct
2	Incorrect	6 ms	4592 KB	Unexpected end of file - int32 expected
3	Incorrect	7 ms	4776 KB	Unexpected end of file - int32 expected
4	Incorrect	7 ms	4776 KB	Unexpected end of file - int32 expected
5	Correct	10 ms	4776 KB	Output is correct
6	Incorrect	10 ms	4972 KB	Unexpected end of file - int32 expected
7	Correct	11 ms	4972 KB	Output is correct
8	Incorrect	17 ms	5172 KB	Unexpected end of file - int32 expected
9	Correct	13 ms	5172 KB	Output is correct
10	Correct	30 ms	5172 KB	Output is correct
11	Correct	16 ms	5172 KB	Output is correct
12	Incorrect	94 ms	5712 KB	Unexpected end of file - int32 expected
13	Incorrect	270 ms	6264 KB	Unexpected end of file - int32 expected
14	Correct	129 ms	6264 KB	Output is correct
15	Incorrect	1650 ms	7220 KB	Unexpected end of file - int32 expected
16	Incorrect	1394 ms	7596 KB	Unexpected end of file - int32 expected
17	Incorrect	1429 ms	7688 KB	Unexpected end of file - int32 expected
18	Correct	133 ms	7688 KB	Output is correct
19	Incorrect	1890 ms	7944 KB	Unexpected end of file - int32 expected
20	Incorrect	1912 ms	8128 KB	Unexpected end of file - int32 expected