Submission #305073

#	Time	Username	Problem	Language	Result	Execution time	Memory
305073		Haunted_Cpp	Stations (IOI20_stations)	C++17	52.32 / 100	1178 ms	1024 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e3 + 5;

vector<vector<int>> g(MAX_N);
int Time = -1, in[MAX_N], out[MAX_N];

void dfs(int node, int p) {
  in[node] = ++Time;
  for (auto to : g[node]) {
    if (to != p) {
      dfs(to, node);
    }
  }
  out[node] = Time;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
  Time = -1;
  g.clear(); g.resize(MAX_N);
	vector<int> labels(n);
  for (int i = 0; i < n - 1; i++) {
    g[u[i]].emplace_back(v[i]);
    g[v[i]].emplace_back(u[i]);
  }
  dfs(0, -1);
  for (int i = 0; i < n; i++) {
    labels[i] = in[i] * 1000 + out[i];
  }
  return labels;
}

pair<int, int> extract(int mask) {
  int out_time = mask % 1000;
  mask /= 1000;
  return make_pair(mask, out_time);
}

bool is_sub(int s, int t) {
  pair<int, int> a= extract(s);
  pair<int, int> b= extract(t);
  return (a.first <= b.first && a.second >= b.second);
}

int find_next_station(int s, int t, vector<int> c) {
  if (is_sub(s, t)) {
    for (auto mask : c) {
      if (is_sub(s, mask) && is_sub(mask, t)) {
        return mask;
      }
    }
    assert(false);
  }
  if (is_sub(t, s)) {
    for (auto mask : c) {
      if (is_sub(t, mask) && is_sub(mask, s)) {
        return mask;
      }
    }
    assert(false);
  }
  for (auto mask : c) {
    if (is_sub(mask, s)) {
      return mask;
    }
  }
  assert(false);
}

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