Cod sursa(job #1264280)

Utilizator oana.claudiaNew Test oana.claudia Data 15 noiembrie 2014 17:52:57
Problema Arbore Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

vector < vector<int> > v;
vector < long > suma;
typedef vector < pair <long,int> > vector_pair;
typedef pair <long, int> long_int_pair;
vector_pair sk;
long_int_pair a;
int n,m;

ifstream f("arbore.in");
ofstream g("arbore.out");

void calc(int p, long s){
    long ss;
    suma[p]+=s;
    ss=suma[p];
    bool gasit=false;
    for(int i=0;i<sk.size()&&!gasit;i++)
        if(sk[i].first==ss)
            gasit=true;
    if(!gasit){
        a.first=suma[p];
        a.second=p;
        sk.push_back(a);
    }
    for(int i=0;i<v[p].size();i++){
        calc(v[p][i],s);
    }


}

int main(){
    int k,x,y,op,p;
    long s;
    f>>n>>m;
    for (int i=0;i<=n;i++){
        v.push_back(vector<int>());
        suma.push_back(0);
    }

    for(int i=1;i<=n-1;i++){
        f>>x>>y;
        if(x>y){
            int aux=x;
            x=y;
            y=aux;
        }
        v[x].push_back(y);
    }

    for(int i=1;i<=m;i++){
        f>>op;
        if(op==1){
            f>>p>>s;
            calc(p,s);
        }
        else {
            f>>s;
            bool gasit=false;
            for(int j=0;j<sk.size()&&!gasit;j++)
                if(sk[j].first==s){
                    gasit=true;
                    g<<sk[j].second<<'\n';
                }
            if(!gasit)
                g<<-1<<'\n';
        }

    }


    f.close();
    g.close();
    return 0;
}