Submission #1293266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293266		julia_08	Stations (IOI20_stations)	C++20	100 / 100	393 ms	584 KiB

stations

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

using namespace std;

const int MAXN = 1e3 + 10;

int pre[MAXN], pos[MAXN], color[MAXN];

vector<int> adj[MAXN];

int t;

void dfs(int v, int p){

  pre[v] = ++t;

  for(auto u : adj[v]){
    if(u != p){
      color[u] = 1 - color[v];
      dfs(u, v);
    }
  }

  pos[v] = ++t;

}

vector<int> label(int n, int k, vector<int> u, vector<int> v){

  t = -1;

  for(int i=0; i<n; i++) adj[i].clear();

  vector<int> labels(n);

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

  color[0] = 0;

  dfs(0, 0);

  vector<pair<int, int>> ord;

  for(int i=0; i<n; i++){
    if(color[i]){
      ord.push_back({pre[i], i});
    } else ord.push_back({pos[i], i});
  }

  sort(ord.begin(), ord.end());

  for(int i=0; i<n; i++) labels[ord[i].second] = i;

  return labels;

}

int find_next_station(int s, int t, vector<int> c){

  sort(c.begin(), c.end());

  if(s < c[0]){

    // s eh pre e todo o resto eh pos

    int pre_s = s, pos_s = s;

    if((int) c.size() > 1) pos_s = c[(int) c.size() - 2];

    if(pre_s <= t && t <= pos_s){

      int pos = lower_bound(c.begin(), c.end(), t) - c.begin();
      return c[pos];
      
    } 

    return c.back();

  }

  // s eh pos e todo o resto eh pre

  int pre_s = s, pos_s = s;

  if((int) c.size() > 1) pre_s = c[1] - 1;

  if(pre_s <= t && t <= pos_s){

    int pos = upper_bound(c.begin(), c.end(), t) - c.begin();
    return c[pos - 1];

  }

  return c[0];

}

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