Cod sursa(job #1332181)

Utilizator diana97Diana Ghinea diana97 Data 1 februarie 2015 19:49:33
Problema Arbore Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 100000 + 1;

int n, m;
int poz, sol;
int v[NMAX];
int stanga[NMAX], dreapta[NMAX];
vector <int> graf[NMAX];
int arb_sum[2 * 4 * NMAX], arb_max[2 * 4 * NMAX];

void citeste() {
    int a, b;

    f >> n >> m;
    for (int i = 1; i < n; i++) {
        f >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
}

void DFS(int nod, int tata) {
    v[++poz] = nod;
    stanga[nod] = poz;
    int l = graf[nod].size();
    for (int i = 0; i < l; i++)
        if (graf[nod][i] != tata) DFS(graf[nod][i], nod);
    v[++poz] = nod;
    dreapta[nod] = poz;
}

void update(int nod, int st, int dr, int x, int val) {
    if (stanga[x] <= st && dr <= dreapta[x]) {
        arb_sum[nod] += val;
        arb_max[nod] = arb_sum[nod] + max(arb_max[2 * nod], arb_max[2 * nod + 1]);
        return;
    }
    int m = (st + dr) / 2;
    if (stanga[x] <= m) update(2 * nod, st, m, x, val);
    if (dreapta[x] > m) update(2 * nod + 1, m + 1, dr, x, val);
    arb_max[nod] = arb_sum[nod] + max(arb_max[2 * nod], arb_max[2 * nod + 1]);
}

void query(int nod, int st, int dr, int suma) {
    if (sol > 0) return;
    if (arb_sum[nod] == suma) {
        sol = v[st];
        return;
    }
    if (st < dr && arb_sum[nod] < suma && arb_max[nod] >= suma) {
        int m = (st + dr) / 2;
        query(2 * nod, st, m, suma - arb_sum[nod]);
        query(2 * nod + 1, m + 1, dr, suma - arb_sum[nod]);
    }
}

void rezolva() {
    int tip, p, s;
    for (int i = 1; i <= m; i++) {
        f >> tip;
        if (tip == 1) {
            f >> p >> s;
            update(1, 1, poz, p, s);
        }
        else {
            sol = -1;
            f >> s;
            query(1, 1, poz, s);
            g << sol << '\n';
        }
    }
}

int main() {
    citeste();
    DFS(1, 0);
    //for (int i = 1; i <= poz; i++) cout << v[i] << ' ';
    rezolva();
}