Submission #1001349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001349		abczz	Rail (IOI14_rail)	C++17	30 / 100	39 ms	644 KiB

rail

#include "rail.h"
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#define ll long long
 
using namespace std;
 
void findLocation(int N, int first, int location[], int stype[])
{
  location[0] = first, stype[0] = 1;
  if (N == 1) return;
  vector <array<ll, 2>> U, V;
  ll A[5000], B[5000], mn = 1e18, id, a = first, b, p;
  for (int i=1; i<N; ++i) {
    A[i] = getDistance(0, i);
    if (mn > A[i]) {
      mn = A[i], id = i;
    }
  }
  b = location[id] = first + mn;
  stype[id] = 2;
  for (int i=0; i<N; ++i) {
    if (i != id) B[i] = getDistance(id, i);
  }
  for (int i=1; i<N; ++i) {
    if (i == id) continue;
    if (A[i] < B[i]) {
      U.push_back({A[i], i});
    }
    else {
      if (B[i] < mn) {
        location[i] = b-B[i];
        stype[i] = 1;
        continue;
      }
      V.push_back({B[i], i});
    }
  }
  sort(U.begin(), U.end());
  sort(V.begin(), V.end());
  p = id;
  for (auto [x, y] : U) {
    auto d = getDistance(y, p);
    if (d + A[p] == x) {
      location[y] = a+A[p]-d;
      stype[y] = 1;
    }
    else {
      location[y] = a+x;
      stype[y] = 2;
      p = y;
    }
  }
  p = 0;
  for (auto [x, y] : V) {
    auto d = getDistance(y, p);
    if (d + B[p] == x) {
      location[y] = b-B[p]+d;
      stype[y] = 2;
    }
    else {
      location[y] = b-x;
      stype[y] = 1;
      p = y;
    }
  }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:22:16: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   22 |   b = location[id] = first + mn;
      |                ^~

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