oj.uz

Submission #55198

# Submission time Handle Problem Language Result Execution time Memory
55198 2018-07-06T09:55:39 Z jklepec Sailing Race (CEOI12_race) C++11
40 / 100
 174 ms 5184 KB 
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())

typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 505;

bool inside(int l, int r, int k, int w) {

  if(w == l || w == r || l == r) return false;

  if(l > r) {
    swap(r, l);
    k ^= 1;
  }

  if(k) {
    return (w > l && r > w);
  }
  return !(w > l && r > w);
}

vector<int> e[MAXN];
int mem[MAXN][MAXN][2];

int calc(int l, int r, int k) {

  if(mem[l][r][k] != -1) {
    return mem[l][r][k];
  }

  int ret = 0;
  for(auto w: e[l]) {
    if(inside(l, r, k, w)) {
      ret = max(ret, 1 + calc(w, r, k));
      ret = max(ret, 1 + calc(w, l, k ^ 1));
    }
  }

  return mem[l][r][k] = ret;
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);

  memset(mem, -1, sizeof mem);

  int n, k; cin >> n >> k;
  assert(k == 0);

  REP(i, n) {
    int x; cin >> x;
    while(x) {
      e[i].push_back(x - 1);

      cin >> x;
    }
  }

  int sol = 0, ind = 1;
  REP(i, n) for(auto j: e[i]) {
    sol = max(sol, calc(j, i, 1));
    sol = max(sol, calc(j, i, 0));
    if(max(calc(j, i, 1), calc(j, i, 0)) == sol) {
      ind = i + 1;
    }
  }

  cout << sol + 1 << endl << ind;
}

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2296 KB Output is correct
2 Runtime error 6 ms 4580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 8 ms 4760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 8 ms 4844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 6 ms 4940 KB Output is correct
6 Runtime error 7 ms 4940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Correct 9 ms 4940 KB Output is correct
8 Runtime error 9 ms 4940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Correct 9 ms 4940 KB Output is correct
10 Correct 21 ms 4940 KB Output is correct
11 Correct 13 ms 5016 KB Output is correct
12 Runtime error 9 ms 5016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 7 ms 5092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Correct 104 ms 5092 KB Output is correct
15 Runtime error 8 ms 5092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 9 ms 5092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 8 ms 5092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Correct 174 ms 5184 KB Output is correct
19 Runtime error 7 ms 5184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 7 ms 5184 KB Execution killed with signal 11 (could be triggered by violating memory limits)