Submission #842615

#	Time	Username	Problem	Language	Result	Execution time	Memory
842615		WLZ	Rail (IOI14_rail)	C++17	100 / 100	92 ms	102688 KiB

rail

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

const int C = 1;
const int D = 2;
const int M = 1e6 + 5;

using namespace std;

void findLocation(int n, int first, int location[], int stype[]) {
  for (int i = 0; i < n; i++) {
    stype[i] = 0;
  }
  vector<int> rev(M, -1);
  location[0] = first;
  stype[0] = C;
  rev[first] = 0;
  vector<vector<int>> dist(n, vector<int>(n, 0));
  vector<int> order(n - 1);
  for (int i = 1; i < n; i++) {
    dist[i][0] = dist[0][i] = getDistance(0, i);
    order[i - 1] = i;
  }
  sort(order.begin(), order.end(), [&](const int& a, const int& b) {
    return dist[0][a] < dist[0][b];
  });
  int c = order[0];
  location[c] = first + dist[0][c];
  stype[c] = D;
  rev[location[c]] = c;
  int j = c;
  for (int i = 1; i < n - 1; i++) {
    int z = order[i];
    dist[c][z] = dist[z][c] = getDistance(c, z);
    if (dist[0][c] + dist[c][z] != dist[0][z]) {
      dist[j][z] = dist[z][j] = getDistance(j, z);
      int k = (dist[0][j] + dist[j][z] - dist[0][z]) >> 1;
      int extra = location[j] - k;
      extra = rev[extra];
      if (extra != -1 && stype[extra] == D) {
        location[z] = location[j] - dist[j][z];
        stype[z] = C;
      } else {
        location[z] = location[0] + dist[0][z]; 
        stype[z] = D;
        j = z;
      }
      rev[location[z]] = z;
    }
  }
  int i = 0;
  order.clear();
  for (int i = 0; i < n; i++) {
    if (i != c) {
      order.emplace_back(i);
    }
  }
  sort(order.begin(), order.end(), [&](const int& a, const int& b) {
    return dist[c][a] < dist[c][b];
  });
  i = 0;
  for (j = 0; j < n - 1; j++) {
    int z = order[j];
    if (dist[0][z] == dist[0][c] + dist[c][z] && dist[0][c] < dist[c][z]) {
      dist[i][z] = dist[z][i] = getDistance(i, z);
      int k = (dist[c][i] + dist[i][z] - dist[c][z]) >> 1;
      int extra = location[i] + k;
      extra = rev[extra];
      if (stype[extra] == C) {
        location[z] = location[i] + dist[i][z];
        stype[z] = D;
      } else {
        location[z] = location[c] - dist[c][z];
        stype[z] = C;
        i = z;
      }
      rev[location[z]] = z;
    }
  }
  for (i = 1; i < n - 1; i++) {
    if (stype[i] == 0) {
      stype[i] = C;
      location[i] = location[c] - dist[c][i];
    }
  }
  return;
}

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