Cod sursa(job #3194934)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 19 ianuarie 2024 19:47:56
Problema Arbore Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cmath>
#define sz 100000
using namespace std;
ifstream fin("arbore.in");
ofstream fout("arbore.out");

vector <int> vec[sz + 5];

int n,m;

int o = 0;
int fr[sz + 5];
int lt[sz + 5];
int iv[2*sz + 5];


int v[sz*2 + 5];


struct bucket
{
    int st = -1;
    int dr = -1;
    unordered_map<int,int> f;
    int ssum=0;
    void update(int st_,int dr_,int val)
    {
        for(int i = st_; i<=dr_; i++)
        {

            f[v[i]]--;
            v[i]+=val;
            f[v[i]]++;
        }
    }
    int query(int val)
    {
        val-=ssum;
        if(f.find(val)==f.end() || f[val]==0)
            return -1;
        for(int i=st;i<=dr;i++)
        {
            if(v[i]==val)
                return iv[i];
        }
    }
}b[600];
int bnr;
int lg;

void update(int nod,int val)
{
    int x = fr[nod];
    int y = lt[nod];
    int st = x/lg + (x%lg!=0);
    if(y<=b[st].dr){
        b[st].update(x,y,val);
        return;
    }
    b[st].update(x,b[st].dr,val);
    st++;
    while(y >= b[st].dr)
    {
        b[st].ssum+=val;
        st++;
    }
    if( y >= b[st].st)
        b[st].update(b[st].st,y,val);
}
int query(int val)
{
    int sol = -1;
    for(int i=1;i<=bnr && sol==-1;i++)
        sol = b[i].query(val);
    return sol;
}



void dfs(int nod,int p)
{
    ++o;
    fr[nod]=o;
    iv[o]=nod;
    for(auto& i : vec[nod])
        if(i!=p)
            dfs(i,nod);
    ++o;
    lt[nod]=o;
    iv[o]=nod;
}


int main()
{
    ios::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    fin>>n>>m;

    for(int i=1; i<n; i++)
    {
        int x,y;
        fin>>x>>y;
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
    dfs(1,0);
    lg = sqrt(o);
    bnr = o/lg + (o%lg!=0);
    for(int i = 1 ; i<=bnr;i++)
    {
        b[i].st=(i-1)*lg+1;
        b[i].dr=i*lg;
        b[i].ssum=0;
        b[i].f[0] = b[i].dr-b[i].st+1;
    }
    b[bnr+1].st=o+1;
    b[bnr+1].dr=o+1;

    for(int i=1;i<=m;i++)
    {
        int tp;
        fin>>tp;
        if(tp==1)
        {
            int p,s;
            fin>>p>>s;
            update(p,s);
        }
        else
        {
            int s;
            fin>>s;
            int sol = query(s);
            fout<<sol<<'\n';
        }
    }
}