Cod sursa(job #1794477)

Utilizator CrystyAngelDinu Cristian CrystyAngel Data 1 noiembrie 2016 12:35:44
Problema Arbore Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <iostream>
#include<cstdio>
#include <vector>

using namespace std;

#define nmax 100100
#define DIM 10000
char buff[DIM];
int poz1=0;

void citeste(int &numar)
{
     numar = 0;
     //cat timp caracterul din buffer nu e cifra ignor
     while (buff[poz1] < '0' || buff[poz1] > '9')
          //daca am "golit" bufferul atunci il umplu
          if (++poz1 == DIM)
               fread(buff,1,DIM,stdin),poz1=0;
     //cat timp dau de o cifra recalculez numarul
     while ('0'<=buff[poz1] && buff[poz1]<='9')
     {
          numar = numar*10 + buff[poz1] - '0';
          if (++poz1 == DIM)
               fread(buff,1,DIM,stdin),poz1=0;
     }
}
vector <int> v[nmax];
vector <int> g[nmax];
int last[nmax];
int arbore[nmax];
int poz[nmax];
int viz[nmax];
int d[nmax];
int s,ans,rad,n,m,i,a,b,q,x,z,k,curr;

void df(int x)
{
    arbore[++k]=x;
    poz[x]=k;
    for(int i=0; i<v[x].size(); ++i)
        df(v[x][i]);
    last[poz[x]]=k;
}

void create(int x)
{
    viz[x]=1;
    for(int i=0; i<g[x].size(); ++i)
        if(!viz[g[x][i]])
        {
            viz[g[x][i]]=1;
            v[x].push_back(g[x][i]);
            create(g[x][i]);
        }
}

int main()
{
    freopen("arbore.in","r",stdin);
    freopen("arbore.out","w",stdout);
    citeste(n);
    citeste(q);
    for(i=1; i<n; ++i)
    {
        citeste(a);
        citeste(b);
        g[a].push_back(b);
        g[b].push_back(a);
    }

    k=0;
    create(1);
    df(1);

    while(q--)
    {
        citeste(x);
        switch(x)
        {
        case 1:
            citeste(z);
            citeste(s);
            d[poz[z]]+=s;
            d[last[poz[z]]+1]-=s;
            break;
        case 2:
            citeste(s);
            curr=0;
            ans=-1;
            for(i=1; i<=n; ++i)
            {
                curr+=d[i];
                if(curr==s)
                {
                    ans=arbore[i];
                    break;
                }
            }
            cout<<ans<<'\n';
            break;
        }
    }
}