Submission #288504

# Submission time Handle Problem Language Result Execution time Memory
288504 2020-09-01T14:35:32 Z rama_pang City (JOI17_city) C++14
100 / 100
609 ms 53432 KB
#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]);
  }
}
#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;
  }
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 1016 KB Output is correct
2 Correct 2 ms 904 KB Output is correct
3 Correct 1 ms 776 KB Output is correct
4 Correct 1 ms 904 KB Output is correct
5 Correct 1 ms 904 KB Output is correct
6 Correct 1 ms 904 KB Output is correct
7 Correct 1 ms 1024 KB Output is correct
8 Correct 1 ms 1016 KB Output is correct
9 Correct 1 ms 904 KB Output is correct
10 Correct 1 ms 1016 KB Output is correct
11 Correct 1 ms 904 KB Output is correct
12 Correct 1 ms 904 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 224 ms 16464 KB Output is correct - L = 164203
2 Correct 208 ms 16440 KB Output is correct - L = 175253
3 Correct 217 ms 16460 KB Output is correct - L = 163319
4 Correct 214 ms 16444 KB Output is correct - L = 164203
5 Correct 586 ms 53408 KB Output is correct - L = 69190238
6 Correct 580 ms 53416 KB Output is correct - L = 69059406
7 Correct 576 ms 53408 KB Output is correct - L = 67458482
8 Correct 585 ms 52960 KB Output is correct - L = 75099557
9 Correct 507 ms 53152 KB Output is correct - L = 115734385
10 Correct 491 ms 52976 KB Output is correct - L = 114567505
11 Correct 506 ms 53224 KB Output is correct - L = 127004943
12 Correct 490 ms 53216 KB Output is correct - L = 114533029
13 Correct 542 ms 53432 KB Output is correct - L = 91405379
14 Correct 581 ms 53256 KB Output is correct - L = 72970222
15 Correct 220 ms 16444 KB Output is correct - L = 169065
16 Correct 215 ms 16700 KB Output is correct - L = 174148
17 Correct 210 ms 16648 KB Output is correct - L = 159120
18 Correct 556 ms 52720 KB Output is correct - L = 120607656
19 Correct 549 ms 52672 KB Output is correct - L = 55249779
20 Correct 561 ms 52656 KB Output is correct - L = 55249779
21 Correct 569 ms 53240 KB Output is correct - L = 114532808
22 Correct 565 ms 53104 KB Output is correct - L = 55873220
23 Correct 574 ms 52864 KB Output is correct - L = 56022395
24 Correct 609 ms 52968 KB Output is correct - L = 55968250
25 Correct 576 ms 52832 KB Output is correct - L = 56427267
26 Correct 587 ms 53416 KB Output is correct - L = 57317676
27 Correct 594 ms 53296 KB Output is correct - L = 57738018