Cod sursa(job #1370050)

Utilizator span7aRazvan span7a Data 3 martie 2015 12:48:01
Problema Arbore Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<fstream>
#include<queue>
#define maxN 100001
using namespace std;
ifstream f("arbore.in");
ofstream g("arbore.out");

vector<int>v[maxN];
int cost[maxN];
queue<int>q;
int p,n;
void solve1(int p,int s)
{
    int cur;
    bool viz[maxN];
    fill(viz+1,viz+n+1,false);
    q.push(p);
    viz[p]=true;
    while(!q.empty())
    {
        cur=q.front();
        cost[cur]+=s;
        q.pop();

        for(int i=0;i<v[cur].size();i++)
            if(viz[v[cur][i]]==0)
        {
             q.push(v[cur][i]);
             viz[v[cur][i]]=1;
        }
    }
}
int solve2(int s)
{
    for(int i=1;i<=n;i++)
        if(cost[i]==s)
            return i;
    return -1;
}
int main()
{
    int a,b,p,s,i,m,t;
    f>>n>>m;
    for(i=1;i<=n-1;i++)
    {
        f>>a>>b;

        v[a].push_back(b);
    }
    for(i=1;i<=m;i++)
    {
        f>>t;
        if(t==1)
        {
            f>>p>>s;
            solve1(p,s);
        }
        else
        {
            f>>s;
            g<<solve2(s)<<'\n';
        }
    }

    return 0;
}