Submission #50673

#	Time	Username	Problem	Language	Result	Execution time	Memory
50673		Just_Solve_The_Problem	Rail (IOI14_rail)	C++17	100 / 100	150 ms	61548 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"

using namespace std;

#define pb push_back
#define eb emplace_back
#define ll long long
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define Ok puts("ok");
#define whatis(x) cerr << #x << " = " << x << endl;
#define pause system("pause");
#define random (rand() ^ (rand() << 15))

const int N = (int)5000 + 7;
const int inf = (int)1e9 + 7;

int dis[N][N];

int getdis(int i, int j) {
  if (i == j) return 0;
  if (dis[i][j] != 0) return dis[i][j];
  dis[i][j] = dis[j][i] = getDistance(i, j);
  return dis[i][j];
}

set < int > sd, su;
pii ar[N];
int sec;

void findLocation(int n, int first, int location[], int stype[]) {
  int L, R;
  for (int i = 1; i < n; i++) {
    ar[i] = mk(getdis(0, i), i);
  }
  sort(ar + 1, ar + n);
  L = 0;
  stype[L] = 1;
  R = ar[1].sc;
  stype[R] = 2;
  location[L] = first;
  location[R] = first + ar[1].fr;
  sec = R;
  set < int > :: iterator to;
  sd.insert(first);
  su.insert(location[R]);
  for (int j = 2; j < n; j++) {
    int i = ar[j].sc;
    int dist = ar[j].fr;
    int distsec = getdis(sec, i);
    if (dist == distsec + ar[1].fr && location[sec] - distsec < first) {
      int distL = getdis(L, i);
      int p = location[L] + distL;
      to = sd.lower_bound(p);
      to--;
      int rr = *to;
      if (location[sec] - rr + p - rr == distsec) {
        stype[i] = 2;
        location[i] = p;
      } else {
        stype[i] = 1;
        location[i] = location[sec] - distsec;
        sd.insert(location[i]);
        L = i;
      }
    } else {
      int distR = getdis(R, i);
      int p = location[R] - distR;
      to = su.upper_bound(p);
      int rr = *to;
      if (rr - first + rr - p == dist) {
        stype[i] = 1;
        location[i] = p;
      } else {
        stype[i] = 2;
        location[i] = first + dist;
        su.insert(location[i]);
        R = i;
      }
    }
  }
//  for (int i = 0; i < n; i++) {
//    cerr << location[i] << ' ';
//  }
//  cerr << '\n';
//  for (int i = 0; i < n; i++) {
//    cerr << stype[i] << ' ';
//  }
//  cerr << '\n';
}

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