Cod sursa(job #931121)

Utilizator tester9x9Tester9x9 tester9x9 Data 27 martie 2013 23:47:36
Problema Arbore Scor 85
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.75 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

#define pb(v, a) v.push_back(a)
#define sz(a) a.size()
#define rep(i, n) for (int i = 0; i < n; ++i)

#define Nmax 100005
#define Rmax 125005

const int buc = 450;

vector< vector<int> > vec;
int n, m, cont, el[2*Nmax], start[Nmax], stop[Nmax], plus[buc], v[2*Nmax];
char mark[Nmax], viz[buc][Rmax];

void readdata()
{
    freopen("arbore.in", "r", stdin);
    freopen("arbore.out", "w", stdout);

    int a, b;

    scanf("%d %d", &n, &m);
    vec.resize(n+1);
    rep(i, n-1)
    {
        scanf("%d %d", &a, &b);
        pb(vec[a], b); pb(vec[b], a);
    }
}

void df(int k)
{
    ++cont;
    start[k] = cont;
    el[cont] = k;

    mark[k] = 1;
    rep(i, sz(vec[k]))
        if (!mark[vec[k][i]])
            df(vec[k][i]);

    ++cont;
    stop[k] = cont;
    el[cont] = k;
}

void update(int nr, int sum)
{
    int a, b, poz, i, jj;

    for (a = 1, b = buc, poz = 0; a <= cont; a = b+1, b+= buc, poz++)
    {
        if (start[nr] > b || stop[nr] < a) continue;
        if (start[nr] <= a && b <= stop[nr]) plus[poz] += sum;
        else
            if (start[nr] >= a)
            {
                jj = min(cont, b);
                for (i = a; i <= jj; ++i)
                    viz[poz][v[i]] = 0;

                jj = min(stop[nr], b);
                for (i = start[nr]; i <= jj; ++i)
                    v[i] += sum;

                jj = min(cont, b);
                for (i = a; i <= jj; ++i)
                    viz[poz][v[i]] = 1;
            }
            else
            {
                jj = min(cont, b);
                for (i = a; i <= jj; ++i)
                    viz[poz][v[i]] = 0;

                for (i = a; i <= stop[nr]; ++i)
                    v[i] += sum;

                for (i = a; i <= jj; ++i)
                    viz[poz][v[i]] = 1;
            }
    }
}

int cauta(int a, int b, int val)
{
    int i;
    for (i = a; i <= b; ++i)
        if (v[i] == val) return el[i];
}

int query(int sum)
{
    int a, b, poz, val;

    for (a = 1, b = buc, poz = 0; a <= cont; a = b+1, b += buc, poz++)
    {
        val = sum-plus[poz];
        if (val >= 0) if (viz[poz][val]) return cauta(a, min(b, cont), val);
    }
    return -1;
}

void solve()
{
    int op, nr, sum;

    for (int i = 0; i < buc; ++i)
        viz[i][0] = 1;
    df(1);

    rep(i, m)
    {
        scanf("%d", &op);
        if (op == 1)
        {
            scanf("%d %d", &nr, &sum);
            update(nr, sum);
        }
        else
        {
            scanf("%d", &sum);
            printf("%d\n", query(sum));
        }
    }
}

int main()
{
    readdata();
    solve();
    return 0;
}