Submission #828214

#	Time	Username	Problem	Language	Result	Execution time	Memory
828214		erray	Stations (IOI20_stations)	C++17	100 / 100	806 ms	724 KiB

stations

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

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
  #include "/home/eagle/ioi20/d2/debug.h"
#else 
  #define debug(...) void(37)
#endif

std::vector<int> label(int N, int k, std::vector<int> U, std::vector<int> V) {
	vector<vector<int>> g(N);
  for (int i = 0; i < N - 1; ++i) {
    g[U[i]].push_back(V[i]);
    g[V[i]].push_back(U[i]);
  }
  debug(g);
  vector<int> label(N), d(N, -1);
  int t = 0;
  function<void(int)> Dfs = [&](int v) {
    if (d[v] % 2 == 0) {
      label[v] = t++;
    }
    for (auto u : g[v]) {
      if (d[u] == -1) {
        d[u] = d[v] + 1;
        Dfs(u);
      }
    }
    if (d[v] % 2 == 1) { 
      label[v] = t++;
    }
  };
  d[0] = 0;
  Dfs(0);
  return label;
}

int find_next_station(int S, int T, std::vector<int> C) {
  debug(S, T, C);
  if (S >= C.back()) {
    if (T > S || T < C[0]) {
      return C[0];
    }
    return C[int(lower_bound(C.begin(), C.end(), T + 1) - C.begin()) - 1];
  } else {
    if (T < S || T > C.back()) {
      return C.back();
    }
    return C[int(lower_bound(C.begin(), C.end(), T) - C.begin())];
  }
}

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