Submission #535013

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <vector>

using namespace std;

template <class Type>
class LCA {
    public:
    
    LCA(int n) : size(n), high(32 - __builtin_clz(n)), graph(n) {
        parent = (int *)malloc(sizeof(int) * size * high);
        depth = (int *)malloc(sizeof(int) * size);
        distance = (Type *)malloc(sizeof(Type) * size);
        minimum = (int *)malloc(sizeof(int) * size * high);
    }
    
    ~LCA() {
        free(parent);
        free(depth);
        free(distance);
        free(minimum);
    }
    
    void add_undirected_edge(int from, int to, Type cost = 1) {
        graph[from].push_back(Edge(to, cost));
        graph[to].push_back(Edge(from, cost));
    }
    
    void init(int *a, int root = 0) {
        dfs(root, -1, 0, 0, a);
        
        for (int i = 0; i + 1 < high; i++) {
            for (int j = 0; j < size; j++) {
                if (parent[j * high + i] == -1) {
                    parent[j * high + i + 1] = -1;
                    minimum[j * high + i + 1] = 1e9 + 1;
                } else {
                    parent[j * high + i + 1] = parent[parent[j * high + i] * high + i];
                    minimum[j * high + i + 1] = min(minimum[j * high + i], minimum[parent[j * high + i] * high + i]);
                }
            }
        }
    }
    
    int lca(int x, int y) {
        if (depth[x] > depth[y]) swap(x, y);
        
        y = up(y, depth[y] - depth[x]);
        
        if (x == y) return x;
        
        for (int i = 31 - __builtin_clz(depth[x]); i >= 0; i--) {
            if (parent[x * high + i] != parent[y * high + i]) {
                x = parent[x * high + i];
                y = parent[y * high + i];
            }
        }
        
        return parent[x * high];
    }
    
    Type dist(int x, int y) {
        return distance[x] + distance[y] - distance[lca(x, y)] * 2;
    }
    
    int up(int x, int y) {
        while (y > 0) {
            int right = __builtin_ctz(y);
            
            x = parent[x * high + right];
            y ^= 1 << right;
        }
        
        return x;
    }
    
    int get(int x, int y) {
        int ans = 1e9 + 1;
        
        while (y > 0) {
            int right = __builtin_ctz(y);
            
            ans = min(ans, minimum[x * high + right]);
            x = parent[x * high + right];
            y ^= 1 << right;
        }
        
        return min(ans, minimum[x * high]);
    }
    
    private:
    
    int size;
    int high;
    int *parent;
    int *depth;
    Type *distance;
    int *minimum;
    
    struct Edge {
        int to;
        Type cost;
        Edge(int to, Type cost) : to(to), cost(cost) {}
    };
    
    vector <vector <Edge> > graph;
    
    void dfs(int now, int par, int dep, Type dist, int *a) {
        parent[now * high] = par;
        depth[now] = dep;
        distance[now] = dist;
        minimum[now * high] = a[now];
        
        for (int i = 0; i < graph[now].size(); i++) {
            if (graph[now][i].to != par) dfs(graph[now][i].to, now, dep + 1, dist + graph[now][i].cost, a);
        }
    }
};

int a[100000];

int main()
{
    int n, q, i;
    
    scanf("%d %d", &n, &q);
    
    for (i = 0; i < n; i++) scanf("%d", &a[i]);
    
    LCA <int> lca(n);
    
    for (i = 0; i < n - 1; i++) {
        int x, y;
        
        scanf("%d %d", &x, &y);
        
        lca.add_undirected_edge(x - 1, y - 1);
    }
    
    lca.init(a);
    
    for (i = 0; i < q; i++) {
        int x, y, z, w, d1, d2;
        
        scanf("%d %d %d", &x, &y, &z);
        
        y--;
        z--;
        
        w = lca.lca(y, z);
        d1 = lca.dist(y, w);
        d2 = lca.dist(z, w);
        
        while (d1 > 0) {
            int l, r, m;
            
            if (lca.get(y, d1) > x) break;
            
            l = -1, r = d1, m = (l + r) / 2;
            
            while (r - l > 1) {
                int p = lca.get(y, m);
                
                if (p <= x) {
                    r = m;
                    m = (l + r) / 2;
                } else {
                    l = m;
                    m = (l + r) / 2;
                }
            }
            
            x %= lca.get(y, r);
            y = lca.up(y, r + 1);
            d1 -= r + 1;
        }
        
        while (d2 > 0) {
            int l, r, m;
            
            if (lca.get(z, d2) > x) break;
            
            l = -1, r = d2, m = (l + r) / 2;
            
            while (r - l > 1) {
                int p = lca.get(lca.up(z, d2 - m), m);
                
                if (p <= x) {
                    r = m;
                    m = (l + r) / 2;
                } else {
                    l = m;
                    m = (l + r) / 2;
                }
            }
            
            x %= lca.get(lca.up(z, d2 - r), r);
            d2 -= r + 1;
        }
        
        x %= a[z];
        
        printf("%d\n", x);
    }
        
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:127:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
                           ^
./Main.cpp:129:47: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < n; i++) scanf("%d", &a[i]);
                                               ^
./Main.cpp:136:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x, &y);
                               ^
./Main.cpp:146:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &x, &y, &z);
                                      ^

Judge Result