Cod sursa(job #1833322)

Utilizator GeanaVladGeana Vlad GeanaVlad Data 22 decembrie 2016 09:45:28
Problema Arbore Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <iostream>
#include<vector>
#include<cstdio>
using namespace std;
vector<int>v[100001],w[100001];
int n,m,i,j,x,y,sum,p,t,S[100001],d[100001],ans;
bool viz[100001];
#define DIM 10000
char buff[DIM];
int poz=0;

void citeste(int &numar)
{
     numar = 0;
     //cat timp caracterul din buffer nu e cifra ignor
     while (buff[poz] < '0' || buff[poz] > '9')
          //daca am "golit" bufferul atunci il umplu
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     //cat timp dau de o cifra recalculez numarul
     while ('0'<=buff[poz] && buff[poz]<='9')
     {
          numar = numar*10 + buff[poz] - '0';
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     }
}
int DFS(int nod,int s)
{
    viz[nod]=1;
    s+=S[nod];
    if(s==sum)
        {
            ans=nod;
            return 1;
        }
    for(int i=0;i<v[nod].size();i++)
        if(!viz[v[nod][i]])
        {
            DFS(v[nod][i],s);
        }
}
void create(int nod)
{
    viz[nod]=1;
    for(int i=0;i<w[nod].size();i++)
        if(!viz[w[nod][i]])
    {
        v[nod].push_back(w[nod][i]);
        create(w[nod][i]);
    }
}
int main()
{
    freopen("arbore.in","r",stdin);
    freopen("arbore.out","w",stdout);
    citeste(n);
    citeste(m);
    for(i=1;i<n;i++)
    {
        citeste(x);
        citeste(y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    //create(1);
    for(i=1;i<=m;i++)
    {
        citeste(t);
        if(t==1)
        {
            citeste(p);
            citeste(sum);
            S[p]+=sum;
        }
        else
        {
            citeste(sum);
            for(j=1;j<=n;j++)
                viz[j]=0;
            ans=-1;
            DFS(1,0);
            cout<<ans<<'\n';
        }
    }
}