Cod sursa(job #910615)

Utilizator vendettaSalajan Razvan vendetta Data 10 martie 2013 21:50:52
Problema Arbore Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.89 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

ifstream f("arbore.in");
ofstream g("arbore.out");

#define nmax 100005
#define ll long long
struct {
    int add, val;
}aint[nmax*4];

int n, m, secv[nmax], P[nmax], U[nmax];
bool viz[nmax];
vector<int> gf[nmax];


void citeste(){
    f >> n >> m;
    int x, y;
    for(int i=1; i<n; ++i){
        f >> x >> y;
        gf[x].push_back(y);
        gf[y].push_back(x);
    }
}

void dfs(int nod){
    viz[nod] =1;
    secv[++secv[0]] = nod;
    P[nod] = secv[0];
    for(int i=0; i<gf[nod].size(); ++i){
        int vc = gf[nod][i];
        if (viz[vc] == 0){
            dfs(vc);
        }
    }
    U[nod] = secv[0];
}

void baga(int nod, int st, int dr, int a, int b, int val){
    if (a <= st && dr <= b){
        aint[nod].add = 1;
        aint[nod].val = val;
        return;
    }
}

void update(int nod, int st, int dr, int a, int b, int val){
    if (a <= st && dr <= b){
        aint[nod].add = 1;
        aint[nod].val += val;
        return;
    }else {
        int mij = (st + dr) / 2;
        if (aint[nod].add != 0){// are informatica
            baga(nod*2, st, mij, st, mij, aint[nod].val);
            baga(nod*2+1, mij+1, dr, mij+1, dr, aint[nod].val);
            aint[nod].add = 0;// a dato
        }
        if (a <= mij) update(nod*2, st, mij, a, b, val);
        if (b > mij) update(nod*2+1, mij+1, dr, a, b, val);
    }
}

void query(int nod, int st, int dr, int a, int b, int &s2){
    if (a <= st && dr <= b ){
        s2 += aint[nod].val;
        return;
    }else {
        int mij = (st + dr) / 2;
        if (aint[nod].add != 0){
            baga(nod*2, st, mij, st, mij, aint[nod].val);
            baga(nod*2+1, mij+1, dr, mij+1, dr, aint[nod].val);
            aint[nod].add = 0;// a datao
        }
        if (a <= mij) query(nod*2, st, mij, a, b, s2);
        if (b > mij) query(nod*2+1, mij+1, dr, a, b, s2);
    }
}

void rezolva(){
    // log n pe prima operatie si o(n*logn) pe a 2-a
    dfs(1);
    //for(int i=1; i<=n; ++i) cout << P[i] << " " << U[i] << "\n";

    int tip, p, s;
    for(int i=1; i<=m; ++i){
        f >> tip;
        if (tip == 1){
            f >> p >> s;
            update(1, 1, n, P[p], U[p], s);// tot subarborele
        }else {
            f >> s;
            int s2 =0; int ok = 0;// pp ca nu e
            for(int j=1; j<=n; ++j){
                s2 = 0;
                query( 1, 1, n, P[j], P[j], s2 );
                if (s2 == s){
                    g << j << "\n";
                    ok = 1;
                    //cout << j << "\n";
                    break;
                }
            }
            if (ok == 0) g << -1 << '\n';
        }
    }
}

int main(){
    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;
}