Cod sursa(job #3240179)

Utilizator PHOSSESSEDProsie Radu-Teodor PHOSSESSED Data 13 august 2024 00:04:31
Problema Arbore Scor 0
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 2.93 kb
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

constexpr int nmax = 1e5 + 1;
constexpr int B = 300;

int lazy[nmax], unde[nmax], sub[nmax], d[nmax], e, val[nmax], s[nmax];
unordered_map<int,int> fr[nmax];  vector<int> g[nmax];

void build(int x, int t = 0)
{
    sub[x] = -e; d[++e] = x; s[x] = e;
    for(auto &it : g[x])
        if(it != t) build(it, x);
    sub[x] += e;

}

int main()
{
    freopen("arbore.in", "r", stdin);
    freopen("arbore.out", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);

    for(int i = B + 1; i < nmax ; i += B)
        unde[i]++;
    for(int i = 1; i < nmax ; i++)
        unde[i] += unde[i-1];
    int n, t, q, a, b; cin >> n >> q;
    for(int i = 1; i < n ; i++)
        {
            cin >> a >> b; fr[unde[i]][0]++;
            g[a].emplace_back(b),
            g[b].emplace_back(a);
        }

    fr[unde[n]][0]++; build(1);
    while(q--)
        {
            cin >> t >> a;
            if(t == 2)
                {

                    bool sem = 0;
                    for(int i = 0 ; i <= unde[n]  && !sem; i++)
                        {

                            if(fr[i].count(a - lazy[i])==0) continue;
                            sem = 1; //cout << lazy[i] << '\n';
                            for(int j = i * B + 1; j <= min(n, (i + 1) * B); j++){
                                if(val[j] + lazy[i] == a)
                                    {
                                        //cout << val[j] << " " << lazy[i] << " " << a << '\n';
                                        cout << s[j] << '\n';
                                        break;
                                    }}
                        }

                    if(!sem) cout << "-1\n";
                }

            else
                {
                    cin >> b;
                    int st = s[a]; int dr = st + sub[a] - 1;
                    //cout << st << " " << dr << " " << unde[st] << " " << unde[dr] << "  ";
                    //cout << "intre ";
                    for(int i = unde[st] + 1; i < unde[dr]; i++) lazy[i] += b;

                    //cout << "   stanga : ";
                    for(int i = st; unde[i] == unde[st] && i <= dr; i++)
                    {
                        //cout << i << " ";
                        fr[unde[i]][val[i]]--; val[i] += b;
                        fr[unde[i]][val[i]]++;
                    }


                    if(unde[st] != unde[dr])
                    {
                       // cout << "  dreapta : ";
                        for(int i = B * unde[dr] + 1; i <= dr; i++){
                           // cout << i << " ";
                            fr[unde[i]][val[i]]--; val[i] += b;
                            fr[unde[i]][val[i]]++;}
                    }

                   // cout << '\n';
                }
        }

}