Submission #524949

#	Time	Username	Problem	Language	Result	Execution time	Memory
524949		Turkhuu	Stations (IOI20_stations)	C++17	100 / 100	997 ms	736 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 < n - 1; i++){
    g[U[i]].push_back(V[i]);
    g[V[i]].push_back(U[i]);
  }
  vector<int> a(n);
  int k = 1;
  function<void(int, int)> dfs = [&](int u, int anc){
    for(int v : g[u]){
      if(v == anc){
        continue;
      }
      a[v] = k++;
      for(int w : g[v]){
        if(w != u){
          dfs(w, v);
        }
      }
    }
    a[u] = k++;
  };
  a[0] = 0;
  for(int v : g[0]){
    dfs(v, 0);
  }
  return a;
}

int find_next_station(int s, int t, vector<int> c){
  int m = (int)c.size();
  if(s > c.back()){
    for(int i = 1; i < m; i++){
      int l = c[i];
      int r = i == m - 1 ? s - 1 : c[i + 1] - 1;
      if(t >= l && t <= r){
        return c[i];
      }
    }
    return c[0];
  } else{
    for(int i = 0; i < m - 1; i++){
      int l = i == 0 ? s + 1 : c[i - 1] + 1;
      int r = c[i];
      if(t >= l && t <= r){
        return c[i];
      }
    }
    return c.back();
  }
}

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