Submission #288504

#	Time	Username	Problem	Language	Result	Execution time	Memory
288504		rama_pang	City (JOI17_city)	C++14	100 / 100	609 ms	53432 KiB

Encoder

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

void Encode(int N, int A[], int B[]) {
  // Euler tour, send information about the left end
  // and the interval length. This scores 30 points.
  // To improve, notice that representing the interval
  // length is wasteful - we can add dummy nodes to
  // force interval lengths into a smaller value range.
  // If we choose to represent the interval lengths by
  // r^0, r^1, r^2, r^3, ..., then the root node's size
  // can be multiplied by a factor of r^d, where d is
  // the depth of the subtree (d <= 18). Thus for the
  // enter time, we have N r^d values, and for the interval
  // length, we have log(N r^d, r) values - thus the maximum
  // value is N r^d log(N r^d, r) = N r^d (log(N, r) + d). 
  // Optimizing this function for N = 250000 and d = 18 yields 
  // r = 1.053 as the optimal ratio, and we need 27.2877 bits.
  // Accounting for integer rounding, this is below the needed
  // 28 bits for perfect score.

  static vector<int> lengths;
  auto GenerateLengths = [&]() {
    if (!lengths.empty()) {
      return;
    }
    const auto OptimalRatio = [&]() {
      const auto Eval = [&](double x) -> double {
        const double MAXN = 250000;
        const double MAXD = 18;
        return MAXN * pow(x, MAXD) * (log(MAXN) / log(x) + MAXD);
      };
      double lo = 1, hi = 2;
      for (int rep = 0; rep < 200; rep++) {
        double md1 = (lo + lo + hi) / 3;
        double md2 = (lo + hi + hi) / 3;
        if (Eval(md1) < Eval(md2)) {
          hi = md2;
        } else {
          lo = md1;
        }
      }
      return lo;
    };

    const int MAXN = 250000;
    const int MAXD = 18;
    const double ratio = OptimalRatio();

    int cur = 1;
    int greater_than_MAXN = 0;
    while (greater_than_MAXN < MAXD) {
      if (cur > MAXN) {
        greater_than_MAXN += 1;
      }
      lengths.emplace_back(cur);
      cur = max(cur + 1,(int) round(cur * ratio));
    }
  };

  vector<vector<int>> adj(N);
  for (int i = 0; i + 1 < N; i++) {
    adj[A[i]].emplace_back(B[i]);
    adj[B[i]].emplace_back(A[i]);
  }
  
  int timer = 0;
  vector<int> st(N), etlen(N);
  function<void(int, int)> Dfs = [&](int u, int p) {
    st[u] = timer++;
    for (auto v : adj[u]) if (v != p) {
      Dfs(v, u);
    }
    etlen[u] = lower_bound(begin(lengths), end(lengths), timer - st[u]) - begin(lengths);
    timer = st[u] + lengths[etlen[u]];
  };

  GenerateLengths();
  Dfs(0, -1);
  for (int i = 0; i < N; i++) {
    Code(i, st[i] * lengths.size() + etlen[i]);
  }
}

Device

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

void InitDevice() {}

int Answer(long long S, long long T) {
  // Euler tour, send information about the left end
  // and the interval length. This scores 30 points.
  // To improve, notice that representing the interval
  // length is wasteful - we can add dummy nodes to
  // force interval lengths into a smaller value range.
  // If we choose to represent the interval lengths by
  // r^0, r^1, r^2, r^3, ..., then the root node's size
  // can be multiplied by a factor of r^d, where d is
  // the depth of the subtree (d <= 18). Thus for the
  // enter time, we have N r^d values, and for the interval
  // length, we have log(N r^d, r) values - thus the maximum
  // value is N r^d log(N r^d, r) = N r^d (log(N, r) + d). 
  // Optimizing this function for N = 250000 and d = 18 yields 
  // r = 1.053 as the optimal ratio, and we need 27.2877 bits.
  // Accounting for integer rounding, this is below the needed
  // 28 bits for perfect score.

  static vector<int> lengths;
  auto GenerateLengths = [&]() {
    if (!lengths.empty()) {
      return;
    }
    const auto OptimalRatio = [&]() {
      const auto Eval = [&](double x) -> double {
        const double MAXN = 250000;
        const double MAXD = 18;
        return MAXN * pow(x, MAXD) * (log(MAXN) / log(x) + MAXD);
      };
      double lo = 1, hi = 2;
      for (int rep = 0; rep < 200; rep++) {
        double md1 = (lo + lo + hi) / 3;
        double md2 = (lo + hi + hi) / 3;
        if (Eval(md1) < Eval(md2)) {
          hi = md2;
        } else {
          lo = md1;
        }
      }
      return lo;
    };

    const int MAXN = 250000;
    const int MAXD = 18;
    const double ratio = OptimalRatio();

    int cur = 1;
    int greater_than_MAXN = 0;
    while (greater_than_MAXN < MAXD) {
      if (cur > MAXN) {
        greater_than_MAXN += 1;
      }
      lengths.emplace_back(cur);
      cur = max(cur + 1,(int) round(cur * ratio));
    }
  };

  GenerateLengths();

  int stx, etlenx, sty, etleny;
  stx = S / lengths.size();
  etlenx = lengths[S % lengths.size()];
  sty = T / lengths.size();
  etleny = lengths[T % lengths.size()];
  
  if (sty <= stx && stx + etlenx <= sty + etleny) {
    return 0;
  } else if (stx <= sty && sty + etleny <= stx + etlenx) {
    return 1;
  } else {
    return 2;
  }
}

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