Submission #55198

#	Time	Username	Problem	Language	Result	Execution time	Memory
55198		jklepec	Sailing Race (CEOI12_race)	C++11	40 / 100	174 ms	5184 KiB

race

#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 / 100