Submission #51045

#	Time	Username	Problem	Language	Result	Execution time	Memory
51045		mirbek01	Rail (IOI14_rail)	C++17	30 / 100	132 ms	40980 KiB

rail

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

using namespace std;

const int N = 5e3 + 2;

int n, dist[N][N], cur;

bool cmp(int a, int b){
      return dist[cur][a] < dist[cur][b];
}

void findLocation(int N, int first, int location[], int stype[]){
      location[0] = first;
      stype[0] = 1;
      if(N == 1) return ;
      vector <int> l, r, v;
      n = N;
      int in = 1;
      for(int i = 1; i < n; i ++){
            dist[0][i] = dist[i][0] = getDistance(0, i);
            if(dist[0][i] < dist[0][in]) in = i;
      }
      location[in] = first + dist[0][in];
      stype[in] = 2;
      for(int i = 1; i < n; i ++){
            if(in == i) continue;
            dist[in][i] = dist[i][in] = getDistance(in, i);
      }
      for(int i = 1; i < n; i ++){
            if(i == in) continue;
            if(dist[in][i] < dist[0][in]){
                  location[i] = location[in] - dist[in][i];
                  stype[i] = 1;
            } else {
                  if(dist[0][in] + dist[in][i] == dist[0][i])
                        l.push_back(i);
                  else
                        r.push_back(i);
            }
      }
      sort(r.begin(), r.end(), cmp);
      for(int i : r){
            bool ok = 1;
            if(!v.empty()){
                  int d = getDistance(i, v.back());
                  int pos = location[v.back()] - d;
                  if(first < pos){
                        int lo;
                        for(int j = 0; j < v.size(); j ++){
                              if(location[v[j]] > pos){
                                    lo = j;
                                    break;
                              }
                        }
                        int x = d - (location[v.back()] - location[v[lo]]);
                        if(dist[0][i] == dist[0][v[lo]] + x){
                              location[i] = location[v[lo]] - x;
                              stype[i] = 1;
                              ok = 0;
                        }
                  }
            }
            if(ok){
                  location[i] = first + dist[0][i];
                  stype[i] = 2;
                  v.push_back(i);
            }
      }
      v.clear();
      cur = in;
      sort(l.begin(), l.end(), cmp);
      for(int i : l){
            bool ok = 1;
            if(!v.empty()){
                  int d = getDistance(i, v.back());
                  int pos = location[v.back()] + d;
                  if(pos < location[in]){
                        int lo;
                        for(int j = 0; j < v.size(); j ++){
                              if(location[v[j]] < pos){
                                    lo = j;
                                    break;
                              }
                        }
                        int x = d - (location[v[lo]] - location[v.back()]);
                        if(dist[in][i] == dist[in][v[lo]] + x){
                              location[i] = location[v[lo]] + x;
                              stype[i] = 2;
                              ok = 0;
                        }
                  }
            }
            if(ok){
                  location[i] = location[in] - dist[in][i];
                  stype[i] = 1;
                  v.push_back(i);
            }
      }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:51:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for(int j = 0; j < v.size(); j ++){
                                        ~~^~~~~~~~~~
rail.cpp:81:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for(int j = 0; j < v.size(); j ++){
                                        ~~^~~~~~~~~~
rail.cpp:80:29: warning: 'lo' may be used uninitialized in this function [-Wmaybe-uninitialized]
                         int lo;
                             ^~
rail.cpp:50:29: warning: 'lo' may be used uninitialized in this function [-Wmaybe-uninitialized]
                         int lo;
                             ^~

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