Submission #1281148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281148		SonicML	Stations (IOI20_stations)	C++20	0 / 100	395 ms	584 KiB

stations

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

int const NMAX = 1000;
std::vector <int> g[1 + NMAX];
int depth[1 + NMAX];
bool visit[1 + NMAX];

int ind;
int rank[1 + NMAX];

void DFS(int node) { 
  visit[node] = true;
  if(depth[node] % 2 == 0) {
    rank[node] = ind;
    ind++;
  }
  for(int i = 0;i < g[node].size();i++) {
    int to = g[node][i];
    if(visit[to] == false) {
      depth[to] = depth[node] + 1;
      DFS(to);
    }
  }
  if(depth[node] % 2 == 1) {
    rank[node] = ind;
    ind++;
  }
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
  std::vector<int> labels;
  labels.resize(n);
  for(int i = 0;i < n-1;i++) {
    int a = u[i];
    int b = v[i];
    g[a].push_back(b);
    g[b].push_back(a);
  }
  DFS(0);
  for(int i = 0;i < n;i++) {
    labels[i] = rank[i];
  }
  return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
  // find if s is in or out label "in" if smallest, "out" if biggest
  sort(c.begin(), c.end());
  //std::cerr << "\"" << s << ' ' << t;
  //for(int i = 0;i < c.size();i++) {
  //  std::cerr << ' ' << c[i];
  //}
  //std::cerr << "\"\n";
  if(s < c[0]) {  // s = in  => c = out
    if(s == 0) { // root, no parent
      for(int i = 0;i < c.size();i++) {
	if(c[i]+1 <= t && t <= c[i+1]) {// v[i+1].in = v[i].out+1 c[i] holds out 
          return c[i+1];
        }
      }
      return c[0]; // c[0] remaining child
    }else {
      // parent is biggest in the c = out case -> c[c.size()-1] = parent  
      for(int i = 0;i+1 < c.size();i++) {
        if(c[i]+1 <= t && t <= c[i+1]) { 
          return c[i+1];
        }
      }
      if(s+1 <= t && t <= c[0]) { // v[0].in = s.in+1
        return c[0];
      } 
      return c[c.size()-1];
    }
  } else { // s = out => c = in -> also no root case
    // parent in 0
    for(int i = 1;i < c.size();i++) {
      if(c[i] <= t && t <= c[i+1]-1) { // c[i].out = c[i+1].in-1
        return c[i];
      } 
    }
    if(c[c.size()-1] <= t && t <= s-1) { // 
      return c[c.size()-1];
    }
    return c[0];
  }
}

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