Submission #1293887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293887		SonicML	Stations (IOI20_stations)	C++20	0 / 100	2089 ms	2162688 KiB

stations

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

using namespace std;

int const NMAX = 1000; 
vector <int> g[1 + NMAX];
int depth[1 + NMAX];

int ind = 0;
int in[1 + NMAX];
int out[1 + NMAX];

void DFS(int node, int parent, vector <int> &labels) {
  if(depth[node] % 2 == 0) {
    ind++;
    labels[node-1] = ind-1;
  } 
  for(int i = 0;i < g[node].size();i++) {
    int to = g[node][i];   
    if(to != parent) {
      depth[to] = depth[node]+1;
      DFS(to, node, labels);
    }
  }
  if(depth[node] % 2 == 1) {
    ind++;
    labels[node-1] = ind-1;
  }
}

void normalize(vector <int> &labels) {
 
  vector <int> aux; 
  for(int i = 0;i < labels.size();i++) { 
    aux.push_back(labels[i]);
  }
  sort(aux.begin(), aux.end());
  aux.erase(unique(aux.begin(), aux.end()), aux.end());
  map <int, int> valToPos;
  for(int i = 0;i < aux.size();i++) {
    valToPos[aux[i]] = i;
  } 
  for(int i = 0;i < labels.size();i++) {
    labels[i] = valToPos[labels[i]];
  }
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
  vector<int> labels(n);
  for(int i = 1;i <= n-1;i++) { 
    int a = u[i-1]+1, b = v[i-1]+1; 
    g[a].push_back(b);
    g[b].push_back(a);
  }
  DFS(1, 1, labels);
  /*
  for(int i = 1;i <= n;i++) {
    if(depth[i] % 2 == 0) { 
      labels[i-1] = in[i];
    }else { 
      labels[i-1] = out[i];
    }
  }
  */
  //normalize(labels);
	return labels;
}

int solve1(int s, int t, vector <int> &c) {
  int oldLim = s;  
  for(int i = 0;i < c.size()-1;i++) {
    if(oldLim < t && t <= c[i]) {
      return c[i]; 
    }
    oldLim = c[i];
  }
  return c[c.size()-1]; 
}

int solve2(int s, int t, vector <int> &c) {
  int oldLim = s;
  for(int i = c.size()-1;i > 0;i--) {
    if(c[i] <= t && t < oldLim) {
      return c[i];
    }
    oldLim = c[i];
  }
  return c[0];
}

int find_next_station(int s, int t, vector<int> c) {
  if(s == 0) { // root / s - in / c - out
    return solve1(s, t, c);
  }else  { // 
    if(s < c[0]) { // s - in / c - out
      return solve1(s, t, c);
    } else { // s - in / c - out
      return solve2(s, t, c);
    }
  }
}

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