Submission #1053045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053045		juicy	City (JOI17_city)	C++17	100 / 100	194 ms	45084 KiB

Encoder

#include "Encoder.h"

#include <bits/stdc++.h>

using namespace std;

namespace {
  const int MAX = 1 << 19;
}

void Encode(int N, int *A, int *B) {
  vector<vector<int>> g(N);
  for (int i = 0; i < N - 1; ++i) {
    g[A[i]].push_back(B[i]);
    g[B[i]].push_back(A[i]);
  }
  int order = 0;
  auto dfs = [&](auto dfs, int u, int p) -> void {
    int tin = order++;
    for (int v : g[u]) {
      if (v ^ p) {
        dfs(dfs, v, u);
      }
    }
    int tout = order, sz = tout - tin, cnt = 0;
    double x = 1, w = 1.05;
    while (x < sz) {
      x *= w;
      ++cnt;
    }
    order = tin + (int) x;
    Code(u, (long long) cnt * MAX + tin);
  };
  dfs(dfs, 0, 0);
}

Device

#include "Device.h"

#include <bits/stdc++.h>

using namespace std;

namespace {
  const int MAX = 1 << 19, N = 300;

  double pw[N];

  array<int, 2> get(long long X) {
    int L = X % MAX, R = L + (int) pw[X / MAX] - 1;
    return {L, R};
  }
}

void InitDevice() {
  pw[0] = 1;
  for (int i = 1; i < N; ++i) {
    pw[i] = pw[i - 1] * 1.05;
  }
}

int Answer(long long S, long long T) {
  auto a = get(S);
  auto b = get(T);
  if (a[0] <= b[0] && b[0] <= a[1]) {
    return 1;
  }
  if (b[0] <= a[0] && a[0] <= b[1]) {
    return 0;
  }
  return 2;
}

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92