Submission #1280901

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280901		SonicML	Stations (IOI20_stations)	C++20	0 / 100	391 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) {
    ind++;
    rank[node] = 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) {
    ind++;
    rank[node] = 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; i++) {
    labels[i] = i;
  }
  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(1);
  for(int i = 0;i < n;i++) {
    labels[i] = rank[i];
  }
  //std::cerr << '\n';
  for(int i = 0;i < n;i++) {
    //std::cerr << "  " << labels[i] << ' ';
  }
  //std::cerr << '\n';
  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
  return 0;
  sort(c.begin(), c.end());
  if(s < c[0]) {  // s = in 
    if(s == 0) { // root, no parent
      for(int i = 1;i < c.size();i++) {
        if(c[i-1] <= t && t <= c[i]-1) { // out c i-1 = (in c i) - 1 
          return c[i-1];
        }
      }    
      return c[c.size()-1];
    }else {
      // c[0] is parent, 
      for(int i = 2;i < c.size();i++) {
	if(c[i-1] <= t && t <= c[i]-1) { // out c i-1 = (in c i) - 1
	  return c[i-1];	
	} 
      }
      // c[c.size()-1] out = s out - 1
      if(c[c.size()-1] <= t && t <= s-1) {
        return c[c.size()-1];
      }
      // if not anything, but parent
      return c[0];
    }
  } else { // s = out
    // no root 
    // parent is in c.size()-1 
    for(int i = 1;i < c.size()-1;i++) {
      if(c[i-1] + 1 <= t && t <= c[i]) { // sorted based on outs, in c[i] = out c[i-1] + 1
        return c[i];
      }
    }
    // in or i = 0 is in s + 1
    if(s + 1 <= t && t <= c[0]) {
      return c[0];
    }
    return c[c.size()-1];
  }
}

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