Submission #1024489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024489		NeroZein	Rail (IOI14_rail)	C++17	56 / 100	1558 ms	100764 KiB

rail

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

void findLocation(int N, int first, int location[], int stype[]) {
  vector<int> cost(N, INT_MAX);
  cost[0] = 0;
  stype[0] = 1; 
  location[0] = first;
  priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq; 
  for (int i = 1; i < N; ++i) {
    int d = getDistance(0, i);
    pq.push({d, 0, i});
    cost[i] = d; 
  }
  vector<bool> vis(N);
  vis[0] = true; 
  while (!pq.empty()) {
    auto [c, v, u] = pq.top();
    pq.pop();
    if (c != cost[u]) {
      continue; 
    }
    vis[u] = true; 
    if (stype[v] == 1) {
      stype[u] = 2;
      location[u] = location[v] + c;      
    } else {
      stype[u] = 1; 
      location[u] = location[v] - c; 
    }
    for (int i = 0; i < N; ++i) {
      if (!vis[i]) {
        int d = getDistance(i, u);
        if (cost[i] > d) {
          cost[i] = d; 
          pq.push({cost[i], u, i});
        }
      }
    }
  }
}

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