Submission #39662

#	Time	Username	Problem	Language	Result	Execution time	Memory
39662		funcsr	Rail (IOI14_rail)	C++14	56 / 100	818 ms	98796 KiB

rail

#include "rail.h"
#include <vector>
#include <iostream>
#include <set>
#include <queue>
#include <algorithm>
#include <cassert>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define MAX_N (1<<19)
#define INF 1145141919
#define all(x) x.begin(), x.end()
#define pb push_back
#define _1 first
#define _2 second

int memo[5000][5000];
int query(int a, int b) {
  if (memo[a][b] != -1) return memo[a][b];
  return memo[a][b] = getDistance(a, b);
}
void findLocation(int N, int first, int location[], int stype[]) {
  rep(i, N) rep(j, N) memo[i][j] = -1;
  rep(i, N) memo[i][i] = 0;
  P m = P(INF, -1);
  rep(i, N) if (i != 0) m = min(m, P(query(0, i), i));
  int a = m._2;
  m = P(INF, -1);
  rep(i, N) if (i != a) m = min(m, P(query(a, i), i));
  int b = m._2;
  location[0] = first;
  location[a] = location[0] + query(0, a);
  location[b] = location[a] - query(a, b);
  stype[a] = 2;
  stype[b] = 1;
  vector<P> ps;
  rep(i, N) if (i != a && i != b) ps.pb(P(query(a, i), i));
  sort(all(ps));
  vector<int> ls, rs;
  for (P pp : ps) {
    int i = pp._2, k = -1;
    if (query(a, i) < query(b, i)) {
      // left
      for (int p : ls) {
        if (query(p, i) + query(a, p) == query(a, i)) {
          k = p;
          break;
        }
      }
      if (k == -1) {
        stype[i] = 1;
        location[i] = location[a] - pp._1;
        ls.pb(i);
      }
      else {
        stype[i] = 2;
        location[i] = location[a] - (pp._1 - query(k, i)*2);
      }
    }
    else {
      // right
      for (int p : rs) {
        if (query(b, p) + query(p, i) == query(b, i)) {
          k = p;
          break;
        }
      }
      if (k == -1) {
        stype[i] = 2;
        location[i] = location[b] + pp._1 - query(a, b);
        rs.pb(i);
      }
      else {
        stype[i] = 1;
        location[i] = location[b] + (pp._1 - query(a, b) - query(k, i)*2);
      }
    }
  }
}

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 26 / 26
• Subtask 4: 0 / 44