Submission #50258

#	Time	Username	Problem	Language	Result	Execution time	Memory
50258		mirbek01	Rail (IOI14_rail)	C++17	56 / 100	1047 ms	99784 KiB

rail

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

using namespace std;

const int N = 5e3 + 2;

int dist[N][N], used[N], Rd[N];

void findLocation(int N, int first, int location[], int stype[]){
      location[0] = first;
      stype[0] = 1;
      if(N <= 1) return ;
      for(int i = 0; i < N; i ++){
            for(int j = i + 1; j < N; j ++){
                  dist[i][j] = dist[j][i] = getDistance(i, j);
            }
      }
      vector <int> rd;
      int a = 1, b = 0;
      for(int i = 2; i < N; i ++){
            if(dist[0][i] < dist[0][a])
                  a = i;
      }
      used[a] = 1;
      rd.push_back(a);
      Rd[a] = 1;
      for(int i = 1; i < N; i ++){
            if(i == a) continue;
            if(dist[a][i] < dist[a][b])
                  b = i;
      }
      if(b){
            used[b] = 1;
            stype[b] = 1;
            location[b] = (location[0] + dist[0][a]) - dist[a][b];
      }
      for(int i = 1; i < N; i ++){
            if(i == a || i == b) continue;
            int fl = 1;
            for(int j = 1; j < N; j ++){
                  if(j == i) continue;
                  if(dist[0][j] + dist[j][i] == dist[0][i]) fl = 0;
            }
            if(fl){
                  rd.push_back(i);
                  Rd[i] = 1;
                  continue;
            }
      }
      for(int i : rd){
            location[i] = dist[0][i] + first;
            stype[i] = 2;
            used[i] = 1;
            Rd[i] = 1;
      }
      for(int i = 1; i < N; i ++){
            if(!used[i]){
                  bool fl = 0;
                  for(int j = 1; j < N; j ++){
                        if(i == j || Rd[j]) continue;
                        if(dist[0][j] + dist[i][j] == dist[0][i])
                              fl = 1;
                  }
                  if(fl) continue;
                  for(int j : rd){
                        if(dist[0][j] + dist[i][j] == dist[0][i]){
                              stype[i] = 1;
                              location[i] = location[j] - dist[i][j];
                              used[i] = 1;
                        }
                  }
            }
      }
      for(int i = 1; i < N; i ++){
            if(!used[i]){
                  int id = 0;
                  for(int j = 0; j < N; j ++){
                        if(j == i) continue;
                        if(dist[i][j] < dist[i][id])
                              id = j;
                  }
                  stype[i] = 2;
                  location[i] = location[id] + dist[i][id];
            }
      }
}

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