Sort by

recency

|

11 Discussions

|

  • + 0 comments

    The problem has a problem: How can the two lines "5 1" and "1 2" both mean 1 is the root? Either we infer that 1 is always the root, or that smaller is always the root, but left --> right clearly doesn't work. The paths clearly have a direction, because if the paths were bidirectional, then any add query would add to all nodes.

  • + 0 comments

    C++ solution

    #include <bits/stdc++.h>
    
    using namespace std;
    
    #define foreach(i, x) for(type(x)i = x.begin(); i != x.end(); i++)
    #define FOR(ii, aa, bb) for(int ii = aa; ii <= bb; ii++)
    #define ROF(ii, aa, bb) for(int ii = aa; ii >= bb; ii--)
    #define type(x) __typeof(x.begin())
    #define pb push_back
    #define mp make_pair
    #define time something_awesome1
    
    const int inf = 1e9;
    const int mod = 1e9 + 7;
    const int logN = 18;
    const int N = 1e5 + 5;
    int start[N], e[N], head[N], time, i, j, k, n, m, depth[N], lca[N][logN + 1];
    int sum[N], x, y, t; 
    char s[5];
    vector<int> v[N];
    
    class node{ 
        public:
            int max, L;
            node(){max = L = 0;}
    } ST[4 * N];
    
    node merge(int l, node x, node y){
        node temp;
        temp.max = max(x.max, y.max);
        temp.max += l;
        temp.L = l;
        return temp;
    }
    
    node update(int k, int bas, int son, int x, int y, int t){
        if(bas > y || son < x) return ST[k];
        if(x <= bas && son <= y){
            ST[k].L += t;
            ST[k].max += t;
            return ST[k];
        }
        int orta = bas + son >> 1;
        return ST[k] = merge(ST[k].L, update(2 * k, bas, orta, x, y, t), update(2 * k + 1, orta + 1, son, x, y, t));
    }
    
    int query(int k, int bas, int son, int x, int y){
        if(bas > y || son < x) return -inf;
        if(x <= bas && son <= y) return ST[k].max;
        int orta = bas + son >> 1;
        return max(query(k + k, bas, orta, x, y), query(k + k + 1, orta + 1, son, x, y)) + ST[k].L;
    }
    
    int dfs(int node, int last){
        lca[node][0] = last;
        foreach(it, v[node])
            if(*it != last){
                depth[*it] = depth[node] + 1;
                sum[node] += dfs(*it,node);
            }
        return ++sum[node];
    }
    
    void dfs2(int node, int last, int s){
        int temp = 0;
        start[node] = ++time;
        head[node] = s;
        foreach(it, v[node]) if(*it != last && sum[*it] > sum[temp]) temp = *it;
        if(temp) dfs2(temp, node, s);
        foreach(it, v[node]) if(*it != last && *it != temp) dfs2(*it, node, *it);
        e[node] = time;
    }
    
    int LCA(int x, int y){
        if(depth[x] < depth[y]) swap(x, y);
        int diff = depth[x] - depth[y];
        FOR(i, 0, logN) if(diff & (1 << i)) x = lca[x][i];
        if(x == y) return x;
        ROF(i, logN, 0) if(lca[x][i] != lca[y][i]) x = lca[x][i], y = lca[y][i];
        return lca[x][0];
    }
    
    int que(int x,int y){
        int mx = -inf;
        while(depth[x] >= depth[y]){
            mx = max(mx, query(1, 1, n, max(start[head[x]], start[y]), start[x]));
            x = lca[head[x]][0]; 
        }
        return mx;
    }
    
    int solve(int x,int y){
        int l = LCA(x, y);
        return max(que(x, l), que(y, l));
    }
    
    int main(){
        scanf("%d", &n);
        FOR(i, 2, n){
            scanf("%d %d", &x, &y);
            v[x].pb(y);
            v[y].pb(x);
        }
        depth[1] = 1;
        dfs(1, 0);
        dfs2(1, 0, 1);
        FOR(j, 1, logN)
            FOR(i, 1, n)
                lca[i][j] = lca[lca[i][j - 1]][j - 1];
        scanf("%d", &m);
        FOR(i, 1, m){
            scanf("%s", s);
            if(strcmp(s, "add") == 0){
                scanf("%d %d", &x, &y);
                update(1, 1, n, start[x], e[x], y);
            }
            else{   
                scanf("%d %d", &x, &y);
                printf("%d\n", solve(x,y));
            } 
        }
        return 0;
    }
    
  • + 0 comments

    2 99 32 99 76 99 33 76

    How to connect them. What is the head of what? What are the sub-nodes of each node?

    Can a node have two heads?

  • + 0 comments

    Submission failed with test case 3, but copy the data into customerized test passed. The 4th line of output should be -1487 instead of 1213 ? Can anyone help me?

  • + 0 comments

    Hey guys i solved the problem using heavy light decomposition incorporating segment tree lazy propagation .

    I managed to secure 112.5/120 point . (with 47/50 test cases passed)

    just three test cases aborted due to i assume because of memory limits

    i again wrote quite well long commented/documented code wchin you can find on submissions abhishek's submsission commented/documented code wchin you can find on submissions [(https://www.hackerrank.com/challenges/subtrees-and-paths/submissions/code/202527244)