Submission #55206

#	Time	Username	Problem	Language	Result	Execution time	Memory
55206		jklepec	Sailing Race (CEOI12_race)	C++11	100 / 100	2303 ms	7524 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, inf = 1e9;

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);
}

int n, K;
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 mem2[MAXN][MAXN][2];
int ravno(int l, int r, int k) {
  if(mem2[l][r][k] != -1) {
    return mem2[l][r][k];
  }

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

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

int dist(int k, int j, int f) {
  int len;
  if(k > j) len = k - j;
  else len = n - j + k;

  if(f) len = n - len;
  return len;
}

int nxt[MAXN][MAXN][2];
void init() {
  memset(nxt, -1, sizeof nxt);
  REP(k, n) for(auto i: e[k]) REP(j, n) REP(f, 2) {
    if(inside(i, j, f, k)) continue;
    if(nxt[i][j][f] == -1 || dist(nxt[i][j][f], j, f) > dist(k, j, f)) {
      nxt[i][j][f] = k;
    }
  }
}

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

  memset(mem, -1, sizeof mem);
  memset(mem2, -1, sizeof mem2);

  cin >> n >> K;

  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;
    }
  }

  sol ++;
  if(!K) {
    cout << sol << endl << ind << endl;
    return 0;
  }

  init();

  REP(i, n) REP(j, n) for(auto l: e[j]) REP(f, 2) {
    int k = nxt[i][j][f];
    if(k == -1 || !inside(j, l, f, k) || !inside(i, j, 1 - f, l)) continue;

//    cout << i _ j _ k _ l _ ravno(i, j, f) << endl;

    int ns = 2 + max(calc(l, k, 1 - f), calc(l, i, f)) + ravno(i, j, f);
    if(ns >= sol) {
      ind = k + 1;
      sol = ns;
    }
  }

  cout << sol << endl << ind << endl;
}

• Subtask 1: 100 / 100