Truck Delivery Solution Google Kickstart 2021

Table of Contents

Problem

Charles is a truck driver in the city of Googleland. Googleland is built in form of a tree with NN nodes where each node represents a city and each edge represents a road between two cities. The cities are numbered 11 to NN. The capital of Googleland is city 11. Each day Charles picks up a load of weight WW in city CC and wants to deliver it to city 11 using the simple path (which is unique) between the cities. Each road ii has a toll which charges amount AiAi if the weight of the load is greater than or equal to a load-limit LiLi.

Charles works for QQ days, where for each day Charles will be given the starting city CC and weight of the load WW. For each day find the greatest common divisor of all the toll charges that Charles pays for that day. If Charles did not have to pay in any of the tolls the answer is 00.

Input

The first line of the input gives the number of test cases, TT. TT test cases follow.

The first line of each test case contains the two integers NN and QQ.

The next N−1N−1 lines describe the roads. ii-th of these lines contains the four space separated integers XX, YY, LiLi and AiAi, indicating a road between cities XX and YY with load-limit LiLi and toll charge AiAi.

The next QQ lines describe the queries. jj-th of these lines contains the two space separated integers CjCj and WjWj representing the starting city and weight of the load on jj-th day.

Output

For each test case, output one line containing Case #xx: yy, where xx is the test case number (starting from 1) and yy is a list of the answers for QQ days in order, separated by spaces.

Limits

Memory limit: 1 GB.
1≤T≤1001≤T≤100.
1≤Li≤2×1051≤Li≤2×105, for all ii.
1≤Ai≤10181≤Ai≤1018, for all ii.
All LiLi are distinct.
2≤Cj≤N2≤Cj≤N, for all jj.
1≤Wj≤2×1051≤Wj≤2×105, for all jj.
It is guaranteed that given roads form a tree.

Test Set 1

Time limit: 20 seconds.
2≤N≤10002≤N≤1000.
1≤Q≤10001≤Q≤1000.

Test Set 2

Time limit: 80 seconds.
2≤N≤5×1042≤N≤5×104 and 1≤Q≤1051≤Q≤105 for at most 2020 test cases.
For the remaining cases, 2≤N≤10002≤N≤1000 and 1≤Q≤10001≤Q≤1000.

Sample

Sample Input

Sample Outpu

Case #1: 1 4 0 5 7
Case #2: 10 5

In Sample Case #1

On the first day, Charles should pay toll charges in the roads between cities (5,3),(3,2)(5,3),(3,2) and (2,1)(2,1). The answer will be gcd(9,8,4)=1gcd(9,8,4)=1.

On the second day, Charles should pay toll charges in the roads between cities (3,2)(3,2) and (2,1)(2,1). The answer will be gcd(8,4)=4gcd(8,4)=4.

On the third day, Charles need not pay toll charges in any of the cities. Thus, the answer will be 00.

In Sample Case #2

On the first day, Charles should pay toll charges in the roads between cities (2,1)(2,1). The answer will be 1010.

On the second day, Charles should pay toll charges in the roads between cities (3,2)(3,2) and (2,1)(2,1). The answer will be gcd(5,10)=5gcd(5,10)=5.

Also Read:

Solution:

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

const int N = 100000, M = 200000;

struct segtree {
segtree *left = nullptr, *right = nullptr;
long long value = 0;

void push() {
    if (!left) {
        left = new segtree();
        right = new segtree();
    }
}

void update(int a, long long x, int l, int r) {
    if (l == r) {
        value = x;
    } else {
        push();
        int m = (l + r) / 2;
        if (a <= m) {
            left->update(a, x, l, m);
        } else {
            right->update(a, x, m + 1, r);
        }
        value = gcd(left->value, right->value);
    }
}

long long query(int a, int b, int l, int r) {
    if (b < l || r < a) {
        return 0;
    } else if (a <= l && r <= b) {
        return value;
    } else {
        push();
        int m = (l + r) / 2;
        return gcd(left->query(a, b, l, m), right->query(a, b, m + 1, r));
    }
}

};

vector> adj[N];
vector> queries[N];
long long ans[N];
segtree *tree;

void dfs(int u, int p = 0) {
for (auto [w, i] : queries[u]) {
ans[i] = tree->query(1, w, 1, M);
}

for (auto [c, l, a] : adj[u]) {
    if (c != p) {
        long long prv = tree->query(l, l, 1, M);
        tree->update(l, gcd(prv, a), 1, M);
        cerr << "add " << l << ", " << a << "\n";
        dfs(c, u);
        tree->update(l, prv, 1, M);
        cerr << "sub " << l << ", " << a << "\n";
    }
}

}

void solve() {
int n, q;
cin >> n >> q;

fill(adj, adj + n + 1, vector<array<long long, 3>>());
for (int i = 0; i < n - 1; ++i) {
    long long u, v, l, a;
    cin >> u >> v >> l >> a;
    adj[u].push_back({v, l, a});
    adj[v].push_back({u, l, a});
}

fill(queries, queries + n + 1, vector<array<int, 2>>());
for (int i = 0; i < q; ++i) {
    int u, w;
    cin >> u >> w;
    queries[u].push_back({w, i});
}

tree = new segtree();

dfs(1);

for (int i = 0; i < q; ++i) {
    cout << ans[i] << " ";
}
cout << "\n";

}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);

int t;
cin >> t;

for (int i = 1; i <= t; ++i) {
    cout << "Case #" << i << ": ";
    solve();
}

}

Truck Delivery Solution Google Kickstart 2021