oj.uz

답안 #55206

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55206 2018-07-06T10:32:07 Z jklepec Sailing Race (CEOI12_race) C++11
100 / 100
 2303 ms 7524 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, 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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4348 KB Output is correct
2 Correct 7 ms 6376 KB Output is correct
3 Correct 9 ms 6512 KB Output is correct
4 Correct 9 ms 6636 KB Output is correct
5 Correct 8 ms 6636 KB Output is correct
6 Correct 11 ms 6636 KB Output is correct
7 Correct 10 ms 6636 KB Output is correct
8 Correct 14 ms 6636 KB Output is correct
9 Correct 12 ms 6636 KB Output is correct
10 Correct 27 ms 6636 KB Output is correct
11 Correct 16 ms 6636 KB Output is correct
12 Correct 111 ms 6672 KB Output is correct
13 Correct 221 ms 6764 KB Output is correct
14 Correct 119 ms 6764 KB Output is correct
15 Correct 1315 ms 6884 KB Output is correct
16 Correct 1567 ms 7108 KB Output is correct
17 Correct 1428 ms 7124 KB Output is correct
18 Correct 153 ms 7124 KB Output is correct
19 Correct 1993 ms 7368 KB Output is correct
20 Correct 2303 ms 7524 KB Output is correct