Sort by

recency

|

7 Discussions

|

  • + 0 comments

    Here is my solution in java, C, C++ HackerRank Tree Splitting Problem Solution

  • + 0 comments

    Here is the solution of Tree Splitting Click Here

  • + 0 comments

    Here is problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-tree-splitting-problem-solution.html

  • + 2 comments

    C++ Solution

    #include<cstdio>
    #include<ctime>
    #include<cstdlib>
    #include<vector>
    
    using namespace std;
    
    int INF, N, M, nr, V, v[400009], ap[200009], t[200009];
    bool scos[200009];
    vector<int> muchii[200009];
    
    struct nod{
        int K, P, nr;
        nod *l, *r, *t;
        nod (int K, int P, int nr, nod *l, nod *r){
            this->nr = nr;
            this->l = l;
            this->r = r;
            this->P = P;
            this->K = K;
            this->t = 0;
        }
    } *adresa1[200009], *adresa2[200009], *nil, *R;
    
    int Rand(){
        return ((rand() % 32768) << 15) + (rand() % 32768) + 1;
    }
    
    void reup(nod *&n){
        if(n->l != nil) n->l->t = n;
        if(n->r != nil) n->r->t = n;
        n->nr = n->l->nr + n->r->nr + 1;
    }
    
    void rot_left(nod *&n){
        nod *t = n->l;
        n->l = t->r, t->r = n;
        t->t = n->t;
        reup(n);
        reup(t);
        n = t;
    }
    
    void rot_right(nod *&n){
        nod *t = n->r;
        n->r = t->l, t->l = n;
        t->t = n->t;
        reup (n);
        reup (t);
        n = t;
    }
    
    void balance(nod *&n){
        if(n->l->P > n->P)
            rot_left(n);
        else if(n->r->P > n->P)
            rot_right(n);
    }
    
    void Insert(nod *&n, int Poz, int K, int P){
        if(n == nil){
            n = new nod(K, P, 1, nil, nil);
            return;
        }
        if(n->l->nr >= Poz) Insert (n->l, Poz, K, P);
        else Insert(n->r, Poz - n->l->nr - 1, K, P);
        reup (n);
        balance (n);
    }
    
    void Erase(nod *&n, int Poz){
        if(n->l->nr >= Poz)
            Erase(n->l, Poz);
        else if(n->l->nr + 1 < Poz)
            Erase(n->r, Poz - n->l->nr - 1);
        else{
            if(n->l == nil && n->r == nil){
                delete n;
                n = nil;
            }
            else{
                if(n->l->P > n->r->P)
                    rot_left (n);
                else
                    rot_right (n);
                Erase(n, Poz);
            }
        }
        if(n != nil) reup (n);
    }
    
    void join(nod *&R, nod *&Rl, nod *&Rr){
        R = new nod(0, 0, Rl->nr + Rr->nr + 1, Rl, Rr);
        Erase(R, Rl->nr + 1);
    }
    
    void split(nod *&R, nod *&Rl, nod *&Rr, int Poz){
        Insert (R, Poz, 0, INF);
        Rl = R->l, Rl->t = 0;
        Rr = R->r, Rr->t = 0;
        delete R, R = nil;
    }
    
    bool nu_radacina(nod *&n){
        if(n->t != 0 && (n->t->l == n || n->t->r == n)) return 1;
        return 0;
    }
    
    void det_root(nod *n, nod *&R){
        while(1){
            if (nu_radacina(n))
                n = n->t;
            else
                break;
        }
        R = n;
    }
    
    int Get_Pos(nod *n){
        int ans = n->l->nr + 1;
        while (1){
            if (nu_radacina(n)){
                if(n->t->l == n) n = n->t;
                else ans += n->t->l->nr + 1, n = n->t;
            }
            else break;
        }
        return ans;
    }
    
    void dfs(int nod){
        ap[nod] = 1;
        v[++nr] = nod;
        for(vector<int>::iterator it = muchii[nod].begin(); it != muchii[nod].end(); it++)
            if (ap[*it] == 0){
                dfs(*it);
                t[*it] = nod;
            }
        v[++nr] = -nod;
    }
    
    void build(nod *&n){
        if(n == nil) return ;
        if(n->K < 0)
            adresa2[-n->K] = n;
        else
            adresa1[n->K] = n;
        build(n->l);
        build(n->r);
    }
    
    void afis(nod *&n){
        if (n == nil) return ;
        afis(n->l);
        printf("%d ", n->K);
        afis(n->r);
    }
    
    void Del(int a, int b){
        if(t[b] == a){
            int aux = a;
            a = b;
            b = aux;
        }
        nod *R, *R1, *R2, *R3, *R4;
        det_root(adresa1[a], R);
        int p1, p2;
        p1 = Get_Pos(adresa1[a]);
        p2 = Get_Pos(adresa2[a]);
        split(R, R4, R3, p2);
        split(R4, R1, R2, p1 - 1);
        R2->t = 0;
        join(R, R1, R3);
    }
    
    int main(){
        srand(time(0));
        INF = (1 << 30) + 7;
        scanf("%d", &N);
        for(int i = 1; i < N; i++){
            int X, Y;
            scanf("%d %d", &X, &Y);
            muchii[X].push_back(Y);
            muchii[Y].push_back(X);
        }
        dfs(1);
        nil = new nod(0, 0, 0, 0, 0);
        R = nil;
        for(int i = 1; i <= nr; i++)
            Insert (R, i - 1, v[i], Rand());
        build(R);
        int V = 0;
        scanf("%d", &M);
        for(int i = 1; i <= M; i++){
            int x;
            scanf("%d", &x), x ^= V;
            nod *R;
            det_root(adresa1[x], R);
            printf("%d\n", R->nr / 2), scos[x] = 1, V = R->nr / 2;
            for(auto it = muchii[x].begin (); it != muchii[x].end (); it ++)
                if (!scos[*it]) Del(x, *it);
        }
        return 0;
    }
    
  • + 1 comment

    Character of the challenging authority is fixed for the individuals. It has been utility of the term and professional college essay writing services are approved for the humans. The flown away item is done for the utilized items for the persons.