Cod sursa(job #1393515)

Utilizator addy01adrian dumitrache addy01 Data 19 martie 2015 15:17:16
Problema Arbore Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.89 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ofstream out ("arbore.out");

const int MAXN = 100000 + 10;

vector <int> Graf[MAXN];

int N, M;
int now;
int H[2 * MAXN];
int First[MAXN], Last[MAXN];
bool Viz[MAXN];
int Sum[MAXN * 4], Max[MAXN * 4];

void DFS (int nod)
{
    now ++;
    H[now] = nod;
    First[nod] = now;
    Viz[nod] = 1;

    vector <int> :: iterator it;
    for (it = Graf[nod].begin (); it != Graf[nod].end (); ++ it)
        if (!Viz[*it]){
            DFS (*it);
            ++ now;
            H[now] = nod;
        }

    Last[nod] = now;
}

void update (int nod, int st, int dr, int a, int b, int val)
{
    if (a <= st && dr <= b){
        Sum[nod] += val;
        Max[nod] = Sum[nod] + max (Max[2 * nod], Max[2 * nod + 1]);

        return;
    }

    int mid = (st + dr) / 2;

    if (a <= mid)
        update (nod * 2, st, mid, a, b, val);
    if (mid < b)
        update (nod * 2 + 1, mid + 1, dr, a, b, val);

    Max[nod] = Sum[nod] + max (Max[2 * nod], Max[2 * nod + 1]);
}

int found;

void query (int nod, int st, int dr, int val)
{
    if (found != -1)
        return;

    if (Sum[nod] == val){
        found = H[st];
        return;
    }

    if (st < dr && Sum[nod] < val && Max[nod] >= val){
        int mid = (st + dr) / 2;
        query (nod * 2, st, mid, val - Sum[nod]);
        query (nod * 2 + 1, mid + 1, dr, val - Sum[nod]);
    }
}

class Reader
{
private:
    ifstream in;
    static const int BUFF_SIZE = (1 << 12);
    char S[BUFF_SIZE];
    int now;

public:
    Reader (const string &file_name)
    {
        in.open (file_name.c_str ());
        in.read (S, BUFF_SIZE);
        now = 0;
    }

    void getBlock ()
    {
        in.read (S, BUFF_SIZE);
        now = 0;
    }

    char getChar ()
    {
        if (now == BUFF_SIZE)
            getBlock ();

        return S[now ++];
    }

    int getInt ()
    {
        int ret = 0;
        char c;

        do{
            c = getChar ();
        } while (!isdigit (c));

        do{
            ret = ret * 10 + c - '0';
            c = getChar ();
        }while (isdigit (c));

        return ret;
    }

    Reader& operator >> (int &X)
    {
        X = getInt ();
        return (*this);
    }
};

Reader in ("arbore.in");

int main()
{
    int i, a, b;
    int op;

    in >> N >> M;
    for (i = 1; i < N; i ++){
        in >> a >> b;
        Graf[a].push_back (b);
        Graf[b].push_back (a);
    }

    DFS (1);

    for (i = 1; i <= M; i ++){
        in >> op;

        if (op == 1){
            in >> a >> b;
            update (1, 1, now, First[a], Last[a], b);
        }
        else{
            in >> a;
            found = -1;
            query (1, 1, now, a);
            out << found << "\n";
        }
    }

    return 0;
}