제출 #540707

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
540707		MilosMilutinovic	기지국 (IOI20_stations)	C++14	100 / 100	796 ms	784 KiB

stations

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

using namespace std;

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
  vector<vector<int>> g(n);
  for (int i = 0; i + 1 < n; i++) {
    g[u[i]].push_back(v[i]);
    g[v[i]].push_back(u[i]);
  }
  vector<int> tin(n), tout(n), lab(n);
  int T = 0;
  function<void(int, int, int)> Dfs = [&](int v, int pv, int d) {
    if (d % 2 == 0) {
      lab[v] = ++T;
    }
    for (int u : g[v]) {
      if (u == pv) {
        continue;
      }
      Dfs(u, v, d ^ 1);
    }
    if (d % 2 == 1) {
      lab[v] = ++T;
    }
  };
  Dfs(0, 0, 0);
  return lab;
}

int find_next_station(int s, int t, vector<int> c) {
  int n = (int) c.size();
  if (n == 1) {
    return c[0];
  }
  for (int i = 0; i < n; i++) {
    if (c[i] == t) {
      return c[i];
    }
  }
  for (int i = 0; i < n; i++) {
    assert(s != c[i]);
  }
  if (s < c[0]) {
    if (t >= s && t <= c[0]) {
      return c[0];
    }
    for (int i = 1; i + 1 < n; i++) {
      if (t > c[i - 1] && t <= c[i]) {
        return c[i];
      }
    }
    return c[n - 1];
  } else {
    assert(s > c[n - 1]);
    if (t >= c[n - 1] && t <= s) {
      return c[n - 1];
    }
    for (int i = n - 2; i > 0; i--) {
      if (t >= c[i] && t < c[i + 1]) {
        return c[i];
      }
    }
    return c[0];
  }
}

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