Cod sursa(job #3148220)

Utilizator AndreiBOTOBotocan Andrei AndreiBOTO Data 29 august 2023 22:30:20
Problema Arbore Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.79 kb
#include <bits/stdc++.h>

#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

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

const int NMAX=1e5+5;
const int SMAX=1e6+5;
const int BMAX=320;

vector<int>v[NMAX];
bitset<SMAX>dp[BMAX];

int lazy[NMAX];
int value[NMAX];
int ti[NMAX];
int to[NMAX];
int ind[NMAX];
int bucket;
int kon;
int n;

void dfs(int p,int tata)
{
    ti[p]=++kon;
    ind[kon]=p;
    for(auto i:v[p])
    {
        if(i!=tata)
            dfs(i,p);
    }
    to[p]=kon;
}

void update(int block,int st,int dr,int val)
{
    int i,j;
    int left,right;
    if(block*BMAX==0)
        left=1;
    else
        left=block*BMAX;
    if((block+1)*BMAX>n+1)
        right=n+1;
    else
        right=(block+1)*BMAX;
    for(i=left;i<right;i++)
        dp[block][value[i]]=false;
    for(i=st;i<=dr;i++)
        value[i]+=val;
    for(i=left;i<right;i++)
        dp[block][value[i]]=true;
}

void update_range(int p,int val)
{
    int i;
    if(ti[p]/BMAX==to[p]/BMAX)
    {
        update(ti[p]/BMAX,ti[p],to[p],val);
        return ;
    }
    else
    {
        update(ti[p]/BMAX,ti[p],(ti[p]/BMAX+1)*BMAX-1,val);
        update(to[p]/BMAX,to[p]/BMAX*BMAX,to[p],val);
        for(i=ti[p]/BMAX;i<to[p]/BMAX;i++)
            lazy[i]+=val;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int q,i,j,x,y;
    fin>>n>>q;
    for(i=1;i<n;i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    bucket=(int)(n/BMAX);
    for(i=0;i<=bucket;i++)
        dp[i][0]=true;
    dfs(1,0);
    while(q--)
    {
        int type;
        fin>>type;
        if(type==1)
        {
            fin>>x>>y;
            update_range(x,y);
        }
        else
        {
            int node=-1;
            fin>>x;
            for(i=0;i<=bucket;i++)
            {
                if(x>lazy[i] && dp[i][x-lazy[i]]==true)
                {
                    int left=i*BMAX;
                    if(left==0)
                        left=1;
                    int right=(i+1)*BMAX;
                    if(right>n+1)
                        right=n+1;
                    for(j=left;j<right;j++)
                    {
                        if(value[j]==x-lazy[i])
                        {
                            node=ind[j];
                            break;
                        }
                    }

                }
                if(node!=-1)
                        break;
            }
            fout<<node<<"\n";
        }
    }
    fin.close();
    fout.close();
    return 0;
}