Submission #308626

#	Time	Username	Problem	Language	Result	Execution time	Memory
308626		szekelymilan	Stations (IOI20_stations)	C++14	31.04 / 100	1020 ms	1272 KiB

stations

#include "stations.h"
#include <vector>

const int P = 2000;

std::vector<std::vector<int>> G;
std::vector<int> labels;
int timeCounter;

void DFS(int node = 0) {
  labels[node] = (timeCounter++) * P;

  for (int v : G[node])
    if (labels[v] == -1)
      DFS(v);
  
  labels[node] += timeCounter++;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
  G.assign(n, std::vector<int>());
  labels.assign(n, -1);
  timeCounter = 0;

  for (int i = 0; i < n - 1; i++) {
    G[u[i]].push_back(v[i]);
    G[v[i]].push_back(u[i]);
  }

  DFS();

  return labels;
}

inline bool inside(int a, int b) {
  return a / P <= b / P && b % P <= a % P;
}

int find_next_station(int s, int t, std::vector<int> c) {
  int parent = -1;

  for (int node : c)
    if (inside(node, s))
      parent = node;
  
  for (int node : c)
    if (node != parent && inside(node, t))
      return node;
  
  return parent;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 16
• Subtask 4: 10 / 10
• Subtask 5: 21.0422 / 61