Cod sursa(job #1018395)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 29 octombrie 2013 15:32:36
Problema Arbore Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.29 kb
#include<fstream>
#include<bitset>
#include<vector>
#include<cmath>

#define NMAX 100002
#define SQRT 320

using namespace std;

ifstream fin("arbore.in");
ofstream fout("arbore.out");

vector<int> G[NMAX];
int n,m,lin[NMAX],first[NMAX],last[NMAX],k,node_val[NMAX];
bool use[NMAX];
bitset<1000001> values[SQRT];

struct piece
{
    int left,right,common;
}v[SQRT];

void read()
{
    fin>>n>>m;
    for(int i=1,x,y;i<n;i++)
    {
        fin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}
/*
void Affis(string fis)
{
    ifstream fout1(fis);

    for(int i = 1; i <= n; i++)
        fout1 << i << " ";

    fout1.close();
}
*/
void DFS(int nod)
{
    use[nod]=1;
    lin[++k]=nod;
    first[nod]=k;
    for(size_t i=0;i<G[nod].size();i++)
        if(!use[G[nod][i]])
            DFS(G[nod][i]);
    last[nod]=k;
}

void split()
{
    k=0;
    for(int i=1,L=(int)sqrtl(n);i<=n;i+=L)
    {
        v[++k].left=i;
        v[k].right=min(i+L-1,n);
        values[k][0]=1;
    }
}

void update(int left,int right,short add)
{
    for(int i=1;i<=k;i++)
    {
        if(v[i].left>right)
            return;
        if(v[i].right<left)
            continue;
        if(left<=v[i].left && v[i].right<=right)
        {
            v[i].common+=add;
            continue;
        }
        for(int j=v[i].left;j<=v[i].right;j++)
        {
            values[i][node_val[j]]=0;
            node_val[j]+=v[i].common;
            if(left<=j && right>=j)
                node_val[j]+=add;
        }
        for(int j=v[i].left;j<=v[i].right;j++)
            values[i][node_val[j]]=1;
        v[i].common=0;
    }
}

int query(int sum)
{
    for(int i=1,Value;i<=k;i++)
    {
        Value=sum-v[i].common;
        if(v[i].common<=sum && values[i][Value])
            for(int j=v[i].left;j<=v[i].right;j++)
                if(Value==node_val[j])
                    return lin[j];
    }
    return -1;
}

void solve()
{
    DFS(1);
    split();
    for(int a,b,c;m;m--)
    {
        fin>>a>>b;
        if(a==1)
        {
            fin>>c;
            update(first[b],last[b],c);
            continue;
        }
        fout<<query(b)<<'\n';
    }
}

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