Submission #443129

#	Time	Username	Problem	Language	Result	Execution time	Memory
443129		peijar	Stations (IOI20_stations)	C++17	100 / 100	1117 ms	776 KiB

stations

#include "stations.h"
#include <algorithm>
#include <bits/stdc++.h>
#include <vector>
using namespace std;

vector<vector<int>> adj;
vector<int> tin, tout;
vector<int> depth;
int curTime;

void dfs(int u, int p) {
  tin[u] = curTime++;
  for (int v : adj[u])
    if (v != p) {
      depth[v] = depth[u] + 1;
      dfs(v, u);
    }
  tout[u] = curTime++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
  curTime = 0;
  tin.clear();
  tout.clear();
  depth.clear();
  adj.clear();
  tin.resize(n), tout.resize(n), adj.resize(n), depth.resize(n);
  for (int i = 0; i < n - 1; ++i) {
    adj[u[i]].push_back(v[i]);
    adj[v[i]].push_back(u[i]);
  }
  dfs(0, 0);
  vector<int> labels(n);
  for (int i = 0; i < n; i++)
    labels[i] = depth[i] % 2 ? tout[i] : tin[i];
  vector<int> dis;
  for (auto l : labels)
    dis.push_back(l);
  sort(dis.begin(), dis.end());
  dis.resize(unique(dis.begin(), dis.end()) - dis.begin());
  for (int &i : labels)
    i = lower_bound(dis.begin(), dis.end(), i) - dis.begin();

  // for (int x : labels)
  // cerr << x << ' ';
  // cerr << endl;
  return labels;
}

int find_next_station(int s, int t, vector<int> c) {
  if (!s) {
    for (int i = 0; i < (int)c.size(); ++i)
      if (t <= c[i])
        return c[i];
  }
  if (c.size() == 1)
    return c[0];
  for (auto v : c)
    if (v == t)
      return v;

  bool allGreater = true, allLess = true;
  for (int i : c)
    allGreater &= i > s, allLess &= i < s;

  if (allGreater) { // s is tin, all others are tout
    int p = c.back();
    c.pop_back();
    if (t < c[0] and t > s)
      return c[0];
    for (int i = 1; i < (int)c.size(); ++i)
      if (t < c[i] and t > c[i - 1])
        return c[i];
    return p;
  } else { // s is tout and all others are tin
    int p = c.front();
    c.erase(c.begin());
    if (t > c.back() and t < s)
      return c.back();
    for (int i = 0; i + 1 < (int)c.size(); ++i)
      if (t > c[i] and t < c[i + 1])
        return c[i];
    return p;
  }
}

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