Cod sursa(job #3194902)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 19 ianuarie 2024 18:52:02
Problema Arbore Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.36 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];


long long v[sz*2 + 5];

bool contains(int st,int dr,int x,int y)
{
    return st<=x && y<=dr;
}

struct bucket
{
    int st;
    int dr;
    unordered_map<long long,vector<int>> f;
    long long ssum=0;

    void update_all(long long val)
    {
        ssum += val;
    }
    void update(int st_,int dr_,long long val)
    {
        for(int i = st_; i<=dr_; i++)
        {
            if(f.find(v[i])!=f.end())
                f[v[i]].pop_back();
            v[i]+=val;
            f[v[i]].push_back(iv[i]);
        }
    }
    int query(long long val)
    {
        if(f.find(val-ssum)==f.end())
            return -1;
        return f[val-ssum].back();
    }
}b[400];
int bnr;
int lg;

void update(int nod,long long val)
{
    int x = fr[nod];
    int y = lt[nod];
    int st = x/lg + (x%lg!=0);
    b[st].update(x,min(y,b[st].dr),val);
    st++;
    while(y >= b[st].dr && st<=bnr)
    {
        b[st].update_all(val);
        st++;
    }
    if(st>bnr)
        return;
    if( y >= b[st].st)
        b[st].update(b[st].st,y,val);
}
int query(long long 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)
{
    fr[nod]=++o;
    iv[o]=nod;
    for(auto& i : vec[nod])
        if(i!=p)
            dfs(i,nod);
    lt[nod]=++o;
    iv[o]=nod;
}


int main()
{
    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;
    }


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