Cod sursa(job #1481495)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 4 septembrie 2015 17:42:59
Problema Arbore Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.59 kb
#include<bits/stdc++.h>
#define Lim 500000
#define Next (++pos==Lim)?(fin.read(Buffer,Lim),pos = 0):0
using namespace std;

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

const int MODULO=10007;
const int NMAX=100005;
const int SQMAX=405;

int n,m,len,sq,eu[NMAX],start[NMAX],stop[NMAX],which[NMAX],pos;
int add[SQMAX],a[NMAX];
vector<int>v[NMAX];
unordered_map<int,int>M[SQMAX];
char Buffer[Lim];

inline void Read(int &x)
{
    bool ok=0;
    while(Buffer[pos]<'0' || '9'<Buffer[pos])
        {
            if (Buffer[pos]=='-') ok=1;
            Next;
        }
    x = 0;
    while('0'<=Buffer[pos] && Buffer[pos]<='9')
    {
        x = x*10 +Buffer[pos]-'0';
        Next;
    }
    if (ok==1) x=-x;
}

inline void Dfs(int x,const int f)
{
    eu[++len]=x;
    start[x]=len;
    for (vector<int>::iterator it=v[x].begin();it!=v[x].end();it++)
        if ((*it)!=f)
            Dfs(*it,x);
    stop[x]=len;
}

inline void Solve(int x,int y,int who,int val)
{
    int i,st,dr;
    M[who].clear();
    for (i=x;i<=y;i++) a[i]+=val;
    dr=min(n,who*sq);st=(who-1)*sq+1;
    for (i=st;i<=dr;i++)
        M[who][a[i]]=eu[i];
}

int main()
{
    int i,j,l,x,y,s,op,aux,poz;
    fin.read(Buffer,Lim);
    Read(n);Read(m);sq=sqrt(n);
    for (i=1;i<n;i++)
        {
            Read(x);Read(y);
            v[x].push_back(y);
            v[y].push_back(x);
        }
    Dfs(1,0);
    for (i=1;i<=n;i++)
        {
            which[i]=(i/sq)+1;
            if (i%sq==0) which[i]--;
            if (which[i]!=which[i-1]) M[which[i]][0]=eu[i];
        }
    for (l=1;l<=m;l++)
        {
            Read(op);
            if (op==1)
                {
                    Read(x);Read(s);
                    i=start[x];y=which[i];
                    if (i%sq!=1)
                        {
                            Solve(i,min(which[i]*sq,stop[x]),which[i],s);
                            i=which[i]*sq+1;
                        }
                    while ((i+sq-1)<=stop[x]) {add[which[i]]+=s;i+=sq;}
                    if (i<=stop[x]) Solve(i,stop[x],which[i],s);
                }
            if (op==2)
                {
                    Read(s);
                    aux=0;poz=-1;
                    for (i=1;i<=n && poz>=0;i+=sq)
                        {
                            aux++;
                            if (M[aux].find(s-add[aux])!=M[aux].end())
                                poz=M[aux][s-add[aux]];
                        }
                    fout<<poz<<"\n";
                }
        }
    return 0;
}