Submission #434397

#	Time	Username	Problem	Language	Result	Execution time	Memory
434397		radaiosm7	Stations (IOI20_stations)	C++17	0 / 100	1142 ms	652 KiB

stations

#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
vector<int> tin;
vector<int> tout;
vector<int> adj[1005];
int timer;
vector<int> labels;

void dfs(int x, int p=-1) {
  tin[x] = timer++;
  for (auto y : adj[x]) {
    if (y != p) dfs(y, x);
  }
  tout[x] = timer++;
}

void give_label(int x, int p=-1, int curr=0) {
  labels[x] = (curr==0)?(tin[x]):(tout[x]);

  for (auto y : adj[x]) {
    if (y != p) {
      give_label(y, x, curr^1);
    }
  }
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
  tin.clear();
  tin.resize(n);
  tout.clear();
  tout.resize(n);

  for (int i=0; i < n; ++i) {
    adj[i].clear();
  }
  timer = 0;
  labels.clear();
  labels.resize(n);

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

  dfs(0);
  give_label(0);

  return labels;
}

int find_next_station(int s, int t, vector<int> c) {
  if ((int)c.size() == 1) {
    return c[0];
  }

  else if (s > c[(int)c.size()-1]) { //Then s is exit time
    if (t > s) {
      return c[0];
    }

    else {
      for (int i=1; i < (int)c.size()-1; ++i) {
        if (c[i] < t && t < c[i+1]) {
          return c[i];
        }
      }

      return c[(int)c.size()-1];
    }
  }

  else {
    if (c[(int)c.size()-2]+1 < t) {
      return c[(int)c.size()-1];
    }

    else {
      for (int i=1; i < (int)c.size(); ++i) {
        if (c[i-1] < t && t < c[i]) {
          return c[i];
        }
      }

      return c[0];
    }
  }
}

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