Submission #169624

#	Time	Username	Problem	Language	Result	Execution time	Memory
169624		AlexLuchianov	Rail (IOI14_rail)	C++14	30 / 100	101 ms	1936 KiB

rail

#include "rail.h"
#include <map>
#include <vector>
#include <algorithm>
#include <iostream>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 5000;
int const inf = 1000000000;

std::map<std::pair<int,int>, int> cost;

int getcost(int x, int y){
  if(cost.find({x, y}) == cost.end())
    cost[{y, x}] = cost[{x, y}] = getDistance(x, y);
  return cost[{x, y}];
}

struct Train{
  int id;
  int dist;
  bool operator < (Train const &a) const{
    return dist < a.dist;
  }
};

void findLocation(int N, int first, int location[], int stype[])
{
  int pos = 1;
  for(int i = 1;i < N; i++)
    if(getcost(0, i) < getcost(0, pos))
      pos = i;
  location[0] = first;
  stype[0] = 1;
  location[pos] = first + getcost(0, pos);
  stype[pos] = 2;
  std::vector<Train> v;
  for(int i = 1; i < N; i++)
    if(i != pos)
      v.push_back({i, getcost(0, i)});
  std::sort(v.begin(), v.end());

  int last1 = 0, last2 = pos;
  int last3 = 0, last4 = pos;
  //std::cout << 0 << " " << location[0] << " " << stype[0] << '\n';
  //std::cout << pos << " " << location[pos] << " " << stype[pos] << '\n';

  for(int i = 0; i < v.size(); i++){
    int id = v[i].id;
    if(getcost(0, id) < getcost(pos, id)){
      //std::cout << "->";

      if((getcost(0, last2) + getcost(last2, id) - 2 * (location[last2] - location[last1])) == getcost(0, id)) {
        location[id] = first + getcost(0, id);
        stype[id] = 2;
        last2 = id;
      } else {
        location[id] = location[last2] - (getcost(last2, id));
        stype[id] = 1;
        if(location[last1] < location[id])
          last1 = id;
      }
    } else {
      //std::cout << "<-";
      int id = v[i].id;
      if(getcost(pos, id) < getcost(0, id)){
        location[id] = location[pos] - getcost(pos, id);
        stype[id] = 1;
      } else {
        if(getcost(pos, last3) + getcost(last3, id) + 2 * (location[last4] - location[last3]) == getcost(pos, id)){
          location[id] = location[pos] - getcost(pos, id);
          stype[id] = 1;
          last3 = id;
        } else {
          location[id] = location[last3] + getcost(last3, id);
          stype[id] = 2;
          if(location[id] < location[last4])
            last4 = id;
        }
      }
    }
    //std::cout << id << " " << location[id] << " " << stype[id] << '\n';
  }
  //std::cout << '\n';
  //for(int i = 0; i < N; i++)
  //  std::cout << stype[i] << " " << location[i] << '\n';
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:51:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v.size(); i++){
                  ~~^~~~~~~~~~

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