Cod sursa(job #2152296)

Utilizator Y0da1NUME JMECHER Y0da1 Data 5 martie 2018 13:38:39
Problema Arbore Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

#define maxn 100005

using namespace std;

int N, M;
vector <int> G [maxn];
int S [maxn];
int precalc [maxn];
bool vizitat [maxn];


int befeu(int s)
{
    memset(vizitat, 0, sizeof(vizitat));
    memset(precalc, 0, sizeof(precalc));

    queue <int> Q;
    int sum = 0;
    //cout<<Q.size()<<"\n";
    Q.push(1);
    vizitat[1] = 1;
    precalc[1] = S[1];

    while(!Q.empty())
    {
        int cur = Q.front();
        //cout<<"Nod curent: "<<cur<<"\n";
        Q.pop();
            //cout<<"Suma curenta: "<<precalc[cur]<<"\n";
        if(precalc[cur] == s)
            return cur;

        for (int i = 0; i < G[cur].size(); ++i)
            if(!vizitat[G[cur][i]])
            {
                Q.push(G[cur][i]);
                vizitat[G[cur][i]] = 1;
                precalc[G[cur][i]] = precalc[cur] + S[G[cur][i]];
            }
    }
    return -1;
}

int main()
{
    ifstream in ("arbore.in");
    ofstream out ("arbore.out");

    in>>N>>M;

    for(int i = 1; i < N; ++i)
    {
        int x, y;
        in>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i = 0; i < M; ++i)
    {
        int t, p, s;
        in>>t;
        if(t == 1)
        {
            in>>p>>s;
            S[p] += s;
        }
        else
        {
            in>>s;
            out<<befeu(s)<<"\n";
        }
    }
    return 0;
}