Cod sursa(job #3196203)

Utilizator Theo20067Cismaru Theodor-Alexe Theo20067 Data 23 ianuarie 2024 09:49:40
Problema Arbore Scor 75
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <map>
#include <cmath>
using namespace std;
ifstream fin ("arbore.in");
ofstream fout("arbore.out");
int n,m,x,T,y,i,Q,k,p,s,rad,nrb,I[200003],first[100003],last[100003],V[200003],S[603];
vector <int> L[100003];
unordered_map <int,int> F[603];
inline int bucket(int x){ return x/rad+(x%rad!=0);}
inline int bucket_start(int x){ return (x-1)*rad+1;}
void dfs(int x,int t)
{
    first[x]=++k;
    I[k]=x;
    for(auto j:L[x])
        if(j!=t)
            dfs(j,x);
    last[x]=++k;
    I[k]=x;
}
void update(int st,int dr,int val)
{
    int st1=bucket(st);
    int dr1=bucket(dr);
    if(st1==dr1)
    {
        for(int j=st;j<=dr;j++)
        {
            F[st1][V[j]]--;
            if(F[st1][V[j]]<=0)
                F[st1].erase(V[i]);
            V[j]+=val;
            F[st1][V[j]]++;
        }
        return;
    }
    for(int j=st;j<bucket_start(st1+1);j++)
    {
        F[st1][V[j]]--;
        if(F[st1][V[j]]<=0)
            F[st1].erase(V[j]);
        V[j]+=val;
        F[st1][V[j]]++;
    }
    for(int j=st1+1;j<dr1;j++)
        S[j]+=val;
    for(int j=bucket_start(dr1);j<=dr;j++)
    {
        F[dr1][V[j]]--;
        if(F[dr1][V[j]]<=0)
            F[dr1].erase(V[j]);
        V[j]+=val;
        F[dr1][V[j]]++;
    }
}
int query(int val)
{
    for(int j=1;j<=nrb;j++)
        if(F[j].find(val-S[j])!=F[j].end())
        {
            for(int l=bucket_start(j);l<bucket_start(j+1);l++)
                if(V[l]+S[j]==val)
                    return I[l];
        }
    return -1;
}
int main()
{
    fin>>n>>m;
    for(i=1;i<n;i++)
    {
        fin>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }
    dfs(1,0);
    rad=sqrt(k);
    nrb=k/rad+(k%rad!=0);
    for(i=1;i<=k;i++)
        F[bucket(i)][0]++;
    for(i=1;i<=m;i++)
    {
        fin>>T;
        if(T==1)
        {
            fin>>p>>s;
            update(first[p],last[p],s);
        }
        else
        {
            fin>>s;
            fout<<query(s)<<"\n";
        }
    }
    return 0;
}