Cod sursa(job #1481509)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 4 septembrie 2015 17:57:58
Problema Arbore Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.99 kb
#include<bits/stdc++.h>
#define mp make_pair
#define PII pair<int,int>
#define fi first
#define se second
#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=37;
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];
vector<PII>H[SQMAX][MODULO];
vector<PII>::iterator pit;
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 Add(int z,int x,int y)
{
    int aux=x%MODULO;
    H[z][aux].push_back(mp(x,y));
}

inline int Cauta(int x,int y)
{
    int aux=y%MODULO;
    for (pit=H[x][aux].begin();pit!=H[x][aux].end();pit++)
        if ((*pit).fi==y)
            return (*pit).se;
    return 0;
}

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;
    for (i=0;i<MODULO;i++) H[who][i].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++)
        Add(who,a[i],eu[i]);
}

int main()
{
    int i,j,l,x,y,s,op,aux,poz,baux;
    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]) Add(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++;
                            baux=Cauta(aux,s-add[aux]);
                            if (baux>0) poz=baux;
                        }
                    fout<<poz<<"\n";
                }
        }
    return 0;
}