Cod sursa(job #3240848)

Utilizator Bianca2507Negret Bianca Bianca2507 Data 21 august 2024 17:42:16
Problema Arbore Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <fstream>
#include <vector>
#include <set>
#include <queue>

using namespace std;
ifstream cin("arbore.in");
ofstream cout("arbore.out");

int n,m,ce,arbore[200005],k,first[100005],last[100005],mars[200005];
bool viz[100005];
vector<int>l[100005];
void dfs(int nod)
{
    viz[nod]=1;
    arbore[++k]=nod;
    first[nod]=k;
    for(int i=0; i<l[nod].size(); i++)
    {
        int vecin=l[nod][i];
        if(viz[vecin]==0)
            dfs(vecin);
    }
    arbore[++k]=nod;
    last[nod]=k;
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n-1; i++)
    {
        int x,y;
        cin>>x>>y;
        l[x].push_back(y);
        l[y].push_back(x);
    }
    dfs(1);
    /**for(int i=1;i<=k;i++)
        cout<<arbore[i]<<" ";
    cout<<'\n';**/
    while(m--)
    {
        int ce;
        cin>>ce;
        if(ce==1)
        {
            int p,s;
            cin>>p>>s;
            mars[first[p]]+=s;
            mars[last[p]+1]-=s;
        }
        else if(ce==2)
        {
            int sum;
            cin>>sum;
            int s=0,sol=-1,ok=1;
            /**for(int i=1;i<=k;i++)
                cout<<mars[i]<<" ";
                cout<< "   ";**/
            for(int i=1; i<=k; i++)
            {
                s+=mars[i];
               // cout<<s<<" ";
                if(s==sum)
                {
                    sol=arbore[i];
                    ok=0;
                }
                if(ok==0)
                   break;

            }
            cout<<sol<<'\n';
        }
    }
    return 0;
}
///liniarizarea arborelui +mars