[Gym] 2018 ACM Amman Collegiate Programming Contest

#	User	Rating
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

The tutorials for problems B & E were written by Reem, D by The-Legend, F by Qumair, J & K by Motarack and M by customer101. Thank you guys for also reviewing the rest of the tutorial!

A. Careful Thief

It’s enough to try all segments of size K that either starts with the start of a range or ends with the end of a range, suppose that the optimal solution is somewhere that starts in some range and ends in some other range (possibly ranges of zeroes), then shifting the segment to one direction will increase the answer, and shifting it in the other direction will decrease it until you reach the boundary of the range, or if both ranges have the same amount of money then shifting will not affect the answer. This can be done using a sorted array of the ranges and for each range that starts with l_i we can binary search for l_i + k - 1 and to get the result of all the ranges in between we can do a prefix summation for (r_i - l_i + 1) × v_i. Same process can be done for trying the ends of all ranges.
Complexity per test-case: $\text{[math]}$ .

Solution

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

struct node {
  int a, b, c;
  node() {}
  node(int a, int b, int c):
    a(a), b(b), c(c) {}
  bool operator < (const node & n) const {
    return a < n.a;
  }
};

int const N = 1e5 + 10;
int t, n, x;
long long cs[N];
node a[N];

int main() {
  scanf("%d", & t);
  while (t-- != 0) {
    scanf("%d %d", & n, & x);
    for (int i = 1; i <= n; ++i)
      scanf("%d %d %d", & a[i].a, & a[i].b, & a[i].c);
    ++n;
    a[n] = node(-1, -1, 0);
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i)
      cs[i] = 1ll * (a[i].b - a[i].a + 1) * a[i].c + cs[i - 1];
    long long best = 0;
    for (int i = 1, nw; i <= n; ++i) {
      nw = a[i].a + x - 1;
      int idx = upper_bound(a + 1, a + n + 1, node(nw, 2e9, 2e9)) - a;
      --idx;
      if (nw >= a[idx].b)
        best = max(best, cs[idx] - cs[i - 1]);
      else
        best = max(best, cs[idx - 1] - cs[i - 1] + 1ll * (nw - a[idx].a + 1) * a[idx].c);
    }
    for (int i = n, nw; i > 0; --i) {
      nw = max(0, a[i].b - x + 1);
      int idx = upper_bound(a + 1, a + n + 1, node(nw, 2e9, 2e9)) - a;
      --idx;
      if (nw <= a[idx].a)
        best = max(best, cs[i] - cs[idx - 1]);
      else
        best = max(best, cs[i] - cs[idx] + 1ll * (a[idx].b - nw + 1) * a[idx].c);
    }
    printf("%lld\n", best);
  }
  return 0;
}

B. Friends and Cookies

This problem simply requires implementation with basic modulus and division calculations. Please observe the following image:

The first iteration, Abood will start to give his friends cookies starting from the 1^st friend, till the n^th. We can simply loop this, since n is maximum 1000. Or add 1 to all friends if x ≥ n. After that, it's just careful calculations. Decrease n from x, and divide what is left by n - 1. This is because in the iterations after the first one, Abood will give cookies to the first n - 1 friends, then to the last n - 1 friends. So by dividing, I can figure out how much each friend will eat without having to loop x times. The only thing left to deal with is $\text{[math]}$ , the remainder cookies. Depending on whether $\text{[math]}$ is even or not, I can figure out the direction of the last iteration, and where I start giving (either start n - 1 and move to the left, or start at 2 and move to the right). Using that, I loop accordingly only the remainder until I have no more cookies left. It is possible to loop because we know the remainder will be less than n - 1. I’m too lazy to discuss exact calculations, if anything is unclear please feel free to write in the comments. Oh and don't forget to clear the array between iterations, and be careful of division by zero when n = 1.
Complexity per test-case: O(N).

Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define se second
#define fi first
#define pb push_back
const int N = 1001;
ll fans[N];

int main() {
  int t, n;
  ll x;
  scanf("%d", &t);
  while (t--) {
    scanf("%lld%d", &x, &n);
    memset(fans, 0, sizeof fans);
    if (n == 1) {
      cout << x << endl;
      continue;
    }
    for (int i = 1; i <= n && x; i++, x--)
      fans[i]++;
    if (x > 0) {
      ll temp = x / (n - 1), rem = x % (n - 1);
      if (temp & 1) {
        fans[1] += temp / 2 + 1, fans[n] += temp / 2;
        for (int i = 2; i < n; i++)
          fans[i] += temp;
        for (int i = 2; i <= n && rem; i++, rem--)
          fans[i]++;
      }
      else {
        fans[1] += temp / 2, fans[n] += temp / 2;
        for (int i = 2; i < n; i++)
          fans[i] += temp;
        for (int i = n - 1; i >= 0 && rem; i--, rem--)
          fans[i]++;
      }
    }
    for (int i = 1; i <= n; i++) {
      printf("%lld", fans[i]);
      if (i != n)
        printf(" ");
    }
    puts("");
  }
  return 0;
}

C. Flip the Bits

The maximal number m which is less than n is n - 1, so the number of flipped bits will be exactly the number of different bits between n and n - 1 which is equal to the number of 1 bits in n XOR (n - 1).
Complexity per test-case: $\text{[math]}$ .

Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
int main(int argc, char* argv[]) {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    printf("%d\n", __builtin_popcount(n ^ (n - 1)));
  }
  return 0;
}

D. Magic Sticks

Let us use these terminologies:

Each line belong to 1 × 1 cell we will call it edge

Each line parallel to one of the biggest rectangle's sides n × m and equal to its length we will call it line.

Our solution depends on these two observations about the selected edges:

They should be parallel to each others.

They should be parallel to the shorter line in the biggest rectangle n × m.

Assume n ≤ m (you can otherwise swap the numbers to satisfy that) And the shorter side n is vertical.
We have m + 1 vertical lines with length n from each one of them if we take an edge then we have to not take the one below or above But how do we select the edges?
We should select them alternatively, why? Let us not take two consecutive edges then there are two cells that are not covered by at least one edge till now so in the next line we must take two consecutive edges to get these two cells covered by at least one edge which will violate the problem's constraints (edges should not touch).
Now let us continue with taking the alternative edges. One of the lines we will take $\text{[math]}$ edges among n, the next one $\text{[math]}$ and so on..
You have to notice that we have to start with taking $\text{[math]}$ from the first line not $\text{[math]}$ since we need to take as much $\text{[math]}$ as we can in comparing with $\text{[math]}$ to minimize the number of edges in the required group.
Here's an example for a 5 × 6 grid:

Complexity per test-case: O(1).

Solution

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

long long n, m, tmp, ans;
int T;

int main(int argc, char** argv) {
  cin >> T;
  while (T--) {
    cin >> n >> m;
    if (n > m)
      swap(n, m);
    tmp = m / 2 + 1;
    ans = tmp * (n / 2) + (m + 1 - tmp) * ((n + 1) / 2);
    cout << ans << endl;
  }
  return 0;
}

E. N-Dimensional Grid

There are many different solutions for this problem that can pass, let's discuss the one where you calculate all pairs and subtract the incorrect ones. For every cell, we need to know how many cells have a manhattan distance of 1 with it. It is clear that these pairs will have the same values for n - 1 dimensions, with only one dimension having a different value by an absolute difference of 1.
So for every cell, keep fixed n - 1 dimensions, and decrease the value for one dimension by 1 will give us one non repeated pair. For each cell, there are n ways to do this. Since number of cells is the product of the sizes of all dimensions in the input, we multiply this product by n to get the number of pairs.
Notice that not all these pairs are valid, because we are considering pairs that get matched with a cell with a 0 as one of its values. All we must do now is decrease these invalid pairs. Fix one dimension with a value as 0. The number of valid cells that will be wrongly matched with this invalid one is the product of all dimensions sizes a_i except for the one that's currently fixed. Therefore for each fixed i, decrease the product of all dimension sizes except for a_i from our number of pairs. This is our final answer.
Complexity per test-case: O(N).

Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define se second
#define fi first
#define pb push_back
const int N = 1e5 + 5, M = 1e9 + 7;
ll v[N], L[N], R[N];

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    scanf("%d", &n);
    long long fans = 0, sum = 1;
    for (int i = 1; i <= n; i++) {
      scanf("%lld", &v[i]);
      sum = (sum * v[i]) % M;
    }
    fans = (sum * n) % M;
    L[0] = R[n + 1] = 1;
    for (int i = 1; i <= n; i++) {
      L[i] = (L[i - 1] * v[i]) % M;
    }
    for (int i = n; i > 0; i--) {
      R[i] = (R[i + 1] * v[i]) % M;
    }
    for (int i = 1; i <= n; i++) {
      long long temp = (L[i - 1] * R[i + 1]) % M;
      fans = (fans - temp + M) % M;
    }
    printf("%lld\n", fans);
  }
  return 0;
}

F. Minimum Sum of Array

Let’s define a frequency array for the original array and a visited array for the values, now for every number x from 1 to 10⁶ with frequency more than zero (it exists in the array) then loop over the multiples of x, if a multiple of x say y is not visited before then we should change y into x as x is the smallest divisor for y in the array.
Complexity per test-case: $\text{[math]}$ .

Solution

#include <bits/stdc++.h>

using namespace std;

int const N = 1e6 + 100;
int const sz = 1e5 + 100;
int t, n, a[sz], freq[N], vis[N];

long long summation() {
  long long sum = 0;
  for (int i = 1; i < N; ++i) {
    if (freq[i]) {
      for (int j = i; j < N; j += i)
        if (freq[j] && !vis[j])
          sum += 1ll * freq[j] * i, vis[j] = 1;
    }
  }
  return sum;
}

int main() {
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
      scanf("%d", &a[i]);
      ++freq[a[i]];
    }

    printf("%lld\n", summation());
    for (int i = 0; i < n; ++i)
      freq[a[i]] = vis[a[i]] = 0;
  }
  return 0;
}

G. Power of String

Notice that the position of the characters doesn't matter because, for example, if you have character ch repeated F_ch times then no matter what their positions are in the string they will add the same value which is equal to $\text{[math]}$ , So we are only interested in F_ch.
Suppose that we have determined what characters we will change, then all of them should be changed to the same character ch₁, and any other equal characters ch should all be changed into ch₁ or none, except for one character ch₂ that we can change part of it, check the proof below.
Now if we will fix ch₁ and ch₂, we can calculate knapsack-like DP on all other characters (we know that we will change either all or none of all equal characters).
Complexity per test-case: O(K × A³) (O(A²) for iterating over (ch₁, ch₂), and O(K × A) for knapsack) where A is equal to the number of different characters in the string which is 26.

Proof

Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5000 + 5, M = 26;
int freq[M], n, k, from, to;
ll dp[N][M], res;
char st[100000 + 5];

ll find(int f, int ch) {
  return f * (f - 1LL) / 2 * (ch + 'a');
}

ll calc(int ch, int rem) {
  if (ch == from || ch == to)
    return calc(ch + 1, rem);
  if (ch == 26) {
    int t = min(rem, freq[from]);
    rem -= t;
    return find(freq[from] - t, from) + find(freq[to] + (k - rem), to);
  }
  ll& ret = dp[rem][ch];
  if (ret != -1)
    return ret;
  ret = find(freq[ch], ch) + calc(ch + 1, rem);
  if (rem - freq[ch] >= 0)
    ret = max(ret, calc(ch + 1, rem - freq[ch]));
  return ret;
}

int main(int argc, char* argv[]) {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d%s", &n, &k, st);
    memset(freq, 0, sizeof freq);
    for (int i = 0; i < n; ++i)
      ++freq[st[i] - 'a'];
    res = 0;
    for (int c1 = 'a'; c1 <= 'z'; ++c1)
      for (int c2 = 'a'; c2 <= 'z'; ++c2) {
        if (c1 == c2)
          continue;
        memset(dp, -1, sizeof dp);
        to = c1 - 'a';
        from = c2 - 'a';
        res = max(res, calc(0, k));
      }
    printf("%lld\n", res);
  }
  return 0;
}

H. Making Friends

Find the maximum value for a_i + a_{2 × n - i - 1} for all i < 2 × n - i - 1.
Complexity per test-case: O(N).

Solution

#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
int n, h[N + N], res;
int main(int argc, char* argv[]) {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    n += n;
    for (int i = 0; i < n; ++i)
      scanf("%d", h + i);
    res = 0;
    for (int i = 0; i < n; ++i)
      res = max(res, h[i] + h[n - i - 1]);
    printf("%d\n", res);
  }
  return 0;
}

I. Split the Number

The minimum difference is either 0 or 1, splitting x equally over the n parts giving each part $\text{[math]}$ , now we have $\text{[math]}$ as left-over which is less than n, we can split them over the last $\text{[math]}$ parts. note that if $\text{[math]}$ equals 0 then there is no strictly positive solution so print - 1.
Complexity per test-case: O(N).

Solution

#include <bits/stdc++.h>
using namespace std;
int T, x, n, d, mod;

int main(int argc, char** argv) {
  cin >> T;
  while (T--) {
    scanf("%d %d", &x, &n);
    d = x / n;
    if (d == 0) {
      puts("-1");
      continue;
    }
    mod = x % n;
    printf("%d", d);
    for (int i = 1; i + mod < n; ++i)
      printf(" %d", d);
    for (int i = 0; i < mod; ++i)
      printf(" %d", d + 1);
    puts("");
  }
  return 0;
}

J. T-Shirts Dilemma

Let a_i, b_i and v_i be the ith bit of a, b and v correspondingly, and let's iterate from the most significant bit to the least significant bit, and each time check the following:

If v_i = 1 and a_i = b_i = 0 then we can take the segment segment [a, b] as their cost will be less than v.
If v_i = 0 and a_i = b_i = 1 then we can't take any number as the cost of every number is greater than v.
If v_i = a_i = b_i = 0 we don't have enough information so we go to the next bit.
If v_i = a_i = b_i = 1 we don't have enough information here either, so we set a_i, b_i and v_i to 0 and go to the next bit (note that flipping the bits won't affect the answer because the OR of any set of numbers before and after the flipping will remain the same expect for the flipped bit, but that bit is the same for v and all numbers in [a, b], so it doesn't matter).
If v_i = a_i = 0 and b_i = 1 then we can't include any number with it's ith bit 1, let c = number with all bits after ith bit 1, and rest of bits 0, then the answer for (a, b, v) equals answer for (a, c, v), so we replace b with c and go to the next bit.
If v_i = 1, a_i = 0 and b_i = 1, if all the bits to the right of the ith bit in v are 1s then we can take the segment [a, b] as our answer, else let c = number with all bits after ith bit 1, and rest of bits 0, then we can either take the segment [a, c] as an answer or take the answer of the problem (c + 1, b, v) with setting the ith bit for all the numbers to 0 (note that we don't benefit by taking the answer of the problem (c, b, v) because c OR (c + 1) is already larger than v), we take the max of those two as our answer.

Cases where a_i = 1 and b_i = 0 are impossible because all the bits to the left of the ith bit are always 0 and b ≥ a. See the code below for better understanding of how the algorithm works.
Complexity per test-case: $\text{[math]}$ .

Solution

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll go(ll a, ll b, ll v, int i = 59) {
  if (i == -1)
    return 1;
  bool ai = a >> i & 1, bi = b >> i & 1, vi = v >> i & 1;
  if (vi && !ai && !bi)
    return b - a + 1;
  if (!vi && ai && bi)
    return 0;
  if (!vi && !ai && !bi)
    return go(a, b, v, i - 1);
  if (vi && ai && bi)
    return go(a & ~(1ll << i), b & ~(1ll << i), v & ~(1ll << i), i - 1);
  if (!vi && !ai && bi)
    return go(a, (1ll << i) - 1, v, i - 1);
  if (v == (1ll << (i + 1)) - 1)
    return b - a + 1;
  ll c = (1ll << i) - 1;
  return max(c - a + 1, go((c + 1) & ~(1ll << i), b & ~(1ll << i), v & ~(1ll << i), i - 1));
}

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    ll a, b, v;
    scanf("%lld%lld%lld", &a, &b, &v);
    printf("%lld\n", go(a, b, v));
  }
}

K. League of Demacia

Let's say that θ is the angle in which Lux will rotate clockwise, and an optimal θ is an angle which will kill the maximum number of soldiers, notice that there could be an infinite amount of optimal θs, but at least one of them will have a soldier intersecting with either the left border of the laser or the left half of the laser's base (the line intersecting with the point (0,0) and having length z), note that this is true because if we take any optimal θ we can keep increasing θ until such soldier appears.
Now let's for each soldier figure out if he can be the chosen one, this can be done by calculating the corresponding θ and counting the number of dead soldiers for such a θ.
let d be the distance of the soldier to the point (0, 0), if $\text{[math]}$ the soldier will intersect with the base, otherwise he will intersect with the left border (imaging a circle at (0, 0) with radius $\text{[math]}$ ).
Let $\text{[math]}$ be vector that resembles the left side of the base and $\text{[math]}$ be a vector from (0, 0) to our soldier, if $\text{[math]}$ then $\text{[math]}$ (in terms of direction), else we can get $\text{[math]}$ by rotating $\text{[math]}$ by θ ₂ counter clockwise, $\text{[math]}$ .

A soldier is dead if he's to the right of $\text{[math]}$ (can be checked using cross product) and he's inside the laser beam (| $\text{[math]}$ after normalizing $\text{[math]}$ , if it's not clear read more about the dot product as this is a classical usage of it).
Complexity per test-case: O(N²).

Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f(i, x, n) for (int i = x; i < (int)(n); ++i)

int const N = 1000;
double const eps = 1e-7;

struct V {
  double x, y;
  V() {}
  void sc() { scanf("%lf%lf", &x, &y); }
  V(double a, double b) : x(a), y(b) { }
  V operator+(V o) { return V(x + o.x, y + o.y); }
  V operator-(V o) { return V(x - o.x, y - o.y); }
  double L() { return sqrt(x * x + y * y); }
  V N() {
    double l = L();
    return V(x / l, y / l);
  }
  V rot(double th) { return V(x * cos(th) - y * sin(th), x * sin(th) + y * cos(th)); }
  V operator*(double z) { return V(x * z, y * z); }
  double operator*(V o) { return x * o.x + y * o.y; }
  double operator|(V o) { return x * o.y - o.x * y; }
  void pr() { printf("%lf %lf\n", x, y); }
} p[N];

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int main() {
  int t;
  cin >> t;
  while (t--) {
    bool dn = false;
    int n, m;
    double z;
    scanf("%d%d%lf", &n, &m, &z);
    z /= 2.0;
    f(i, 0, n) p[i].sc();
    f(i, 0, n) {
      V dv = p[i];
      double l = dv.L();
      V c;
      if (l <= z)
        c = dv.N();
      else {
        double th = acos(z / l);
        c = dv.rot(th).N();
      }
      int ins = 1;
      f(j, 0, n) if (i != j) {
        V d = p[j];
        double t = abs(d * c);
        if (t - eps <= z && (d | c) > -eps)
          ++ins;
      }
      if (ins >= m) {
        printf("Yes\n");
        dn = true;
        break;
      }
    }
    if (!dn)
      printf("No\n");
  }
}

L. Lazy Teacher

The problem can be solved using Dynamic Programming, the DP state is dp[i][j][p1][p2][p3][p4][p5] which i and j means at the i^th row and j^th column and the colors of the last 5 cells are p_i where p₁ is the earliest one and p₅ is the latest one, that is because only the last 5 cells colored will affect the result if we move column by column making sure no two adjacent cells have the same color.
Now p_i values can reach 10⁵ each, but some different coloring patterns have the same result, for example if you have the colors 5, 9, 5, 2, 1 for p₁, p₂, p₃, p₄, p₅ the answer for dp[i][j][p1][p2][p3][p4][p5] will be the same for the colors 0, 1, 0, 2, 3 which means mapping the colors to smaller numbers in a smart way will make: p₁ < 1, p₂ < 2, p₃ < 3, p₄ < 4, p₅ < 5 while giving the same result, this way we only need to try colors from 0 to 4, and the rest from 5 to k will give the same answer as they will have the same mapping so in the DP we only need to iterate over min(k, n + 1) colors.
Complexity per test-case: O(N² × M × N!), the extra N is from the loop inside the DP.

Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10000 + 1, M = 5 + 1, MOD = 1000000007;
int dp[M][N][2][3][4][5];
int n, m, k, lim;

int p[5], vl[6];
void fix() {
  memset(vl, 0, sizeof vl);
  for (int i = 0, idx = 1; i < 5; ++i) {
    if (vl[p[i]] != 0)
      p[i] = vl[p[i]] - 1;
    else
      vl[p[i]] = idx, p[i] = idx++ - 1;
  }
}

int calc(int i, int j, int p2, int p3, int p4, int p5) {
  if (i == n)
    return calc(0, j + 1, p2, p3, p4, p5);
  if (j == m)
    return 1;
  int& ret = dp[i][j][p2][p3][p4][p5];
  if (ret != -1)
    return ret;
  ret = 0;
  int lft = (n == 5 ? 0 : (n == 4 ? p2 : (n == 3 ? p3 : (n == 2 ? p4 : p5))));
  for (int val = 0; val < lim; ++val) {
    if (val == lft && j != 0)
      continue;
    if (val == p5 && i != 0)
      continue;
    p[0] = p2, p[1] = p3, p[2] = p4, p[3] = p5, p[4] = val;
    fix();
    ret = (ret + (val == 5 ? k - 5LL : 1LL) * calc(i + 1, j, p[1], p[2], p[3], p[4])) % MOD;
  }
  return ret;
}

int main(int argc, char* argv[]) {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d%d", &n, &m, &k);
    lim = min(k, 6);
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < m; ++j)
        memset(dp[i][j], -1, sizeof dp[i][j]);
    printf("%d\n", calc(0, 0, 0, 0, 0, 0));
  }
  return 0;
}

M.Greedy Pirate

It's obvious that we need to traverse the maximum number of edges. Let's denote u as the starting node and v as the finishing node, the only edges that we can not traverse are the edges on the path directed from v to u, so we need to calculate the sum of coins on this path and then subtract it from the total number of coins on all edges. Calculating the sum of coins on a path can be done easily by finding the lowest common ancestor(LCA) of node u and node v, the answer will be: cost₁(u) - cost₁(lca) + cost₂(v) - cost₂(lca) where cost₁(x) is the cost of the directed path from the root to x and cost₂(x) is the cost of the directed path from x to the root which can be pre-calculated with a DFS.
Complexity per test-case: $\text{[math]}$ .

Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
int const N = 1e5 + 10, oo = 1e9;
int mod = oo + 7;
ll const OO = 1e18;
int t, n, q;
vector<vector<int> > from_root, dp;
vector<int> dep;
vector<vector<pair<int, pp> > > adj;

void dfs(int u, int p = 0, ll cs1 = 0, ll cs2 = 0) {
  from_root[0][u] = cs1;
  from_root[1][u] = cs2;
  dp[u][0] = p;
  for (auto v : adj[u]) {
    if (v.first == p)
      continue;
    int a = v.second.first, b = v.second.second;
    dep[v.first] = dep[u] + 1;
    dfs(v.first, u, cs1 + a, cs2 + b);
  }
}

int lca(int a, int b) {
  if (dep[a] > dep[b])
    swap(a, b);
  for (int i = 18; i > -1; i--)
    if (dep[b] - (1 << i) >= dep[a])
      b = dp[b][i];
  if (b == a)
    return a;
  for (int i = 18; i > -1; i--) {
    if (dp[a][i] != dp[b][i]) {
      a = dp[a][i];
      b = dp[b][i];
    }
  }
  return dp[a][0];
}

int main() {
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    dp = vector<vector<int> >(n + 1, vector<int>(19));
    from_root = vector<vector<int> >(2, vector<int>(n + 1));
    dep = vector<int>(n + 1);
    adj = vector<vector<pair<int, pp> > >(n + 1);
    ll sumAll = 0;
    for (int i = 0; i < n - 1; i++) {
      int u, v, a, b;
      scanf("%d%d%d%d", &u, &v, &a, &b);
      adj[u].push_back({ v, { a, b } });
      adj[v].push_back({ u, { b, a } });
      sumAll += a + b;
    }
    dfs(1);
    scanf("%d", &q);
    for (int j = 1; j < 19; j++)
      for (int i = 1; i <= n; i++)
        if (dp[i][j - 1])
          dp[i][j] = dp[dp[i][j - 1]][j - 1];
    while (q--) {
      int u, v;
      scanf("%d%d", &u, &v);
      int lc = lca(u, v);
      printf("%lld\n", sumAll - from_root[1][v] + from_root[1][lc] - from_root[0][u] + from_root[0][lc]);
    }
  }
  return 0;
}

Comments (8)

Show archived | Write comment?

O.S.Mozes

6 years ago, # |

+18

I am sorry but I do not understand why the complexity of the last problem (M) is N² per test case. It seems to me it's only Nlog(N). May you please explain?

Thank you.

→ Reply

Vendetta.

6 years ago, # ^ |

It is actually $\text{[math]}$ , welcome to the copy paste world! Just edited it, Thanks!

sOuI

Can i know what is the second case in problem B :( I wrote a math equation to solve this problem ,but it seems that something wrong. Can I get any help?

Here my code https://ideone.com/V5Sxh6 Thanks a lot.

The-Legend

Your solution is correct, but the problem is in using double numbers, and that might give you inconsistent results, try to write your own ceil function which doesn't deal with float numbers.

I've just updated your solution code`

← Rev. 6 →

Could you please explain more why it is a problem ? btw, in the updated code i try to understand how (x-i+1 + 2*n-3) / (2*n — 2) is equivalent to ceil((x-i+1)/(2.0*(n-1))) ,but for sorry i could not.
i will be happier with more explanation

Again, thanks!

← Rev. 3 →

The problem is caused by the limited storage for floating point numbers (double numbers).

For example $\text{[math]}$ is equal to 0.3333333333333..., after a digit the number will be cut and some round will occur then.

So for example if you want to divide 4.0 by 2.0 you might end up with 2.0000000001 (just an example) and then after you take a ceiling to this number you will get 3.

I advise you to read more about precision errors in floating point numbers for complete understanding about the problem.

Now the ceil function to this fraction $\text{[math]}$ is equal to :

$\text{[math]}$ if $\text{[math]}$ , i.e $\text{[math]}$ .
$\text{[math]}$ (integer division) if $\text{[math]}$

please note that we are talking about ceil when dividing two positive numbers.

Now there is another way to write the ceil function $\text{[math]}$ How is that true ? Let us assume there is a remainder x ≥ 1 when dividing a by b then if we add b-1 to x this will increase the integer division result by 1 (the first part above) since b - 1 + x ≥ b since x ≥ 1, the other case when there is no remainder when divide a by b then adding b-1 to the numerator has no affect in the result (the second part above)

So I just added the denominator - 1 to the numerator at your solution.

wonderful! Thanks for the useful reply.

MidoriFuse

I really like the solution code for E. I calculated inverse for all 1e5 values, which took 1528ms. The solution code doesn't even use inverse.