Submission #959649

#	Time	Username	Problem	Language	Result	Execution time	Memory
959649		vjudge1	Rail (IOI14_rail)	C++17	8 / 100	244 ms	98424 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 5e3;

int n, dis[N][N];

void findLocation(int NN, int first, int location[], int stype[]) {
  n = N;

  for (int i = 0; i < n; i++) {
    dis[i][i] = 0;
    for (int j = i+1; j < n; j++) {
      dis[i][j] = dis[j][i] = getDistance(i, j);
    }
  }

  /*
  encuentro la estacion mas próxima, estara a la derecha y será x
  para cualquier otra estación, o bien pasará por x y luego irá hacia la izquierda 
  o bien será ir solo hacia la derecha
  */

  int x = 1;
  int mn = dis[0][1];
  for (int i = 2; i < n; i++) {
    if (dis[0][i] < mn) {
      mn = dis[0][i];
      x = i;
    }
  }

  stype[0] = 1;
  location[0] = first;
  stype[x] = 2;
  location[x] = first + dis[0][x];
  for (int i = 1; i < n; i++) {
    if (i == x) continue;

    if (dis[0][i] == dis[0][x] + dis[x][i]) {
      stype[i] = 1;
      location[i] = location[x] - dis[x][i];
    }
    else {
      stype[i] = 2;
      location[i] = first + dis[0][i];
    }
  }
}

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