Cod sursa(job #3240131)

Utilizator PHOSSESSEDProsie Radu-Teodor PHOSSESSED Data 12 august 2024 18:16:09
Problema Arbore Scor 0
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 2.79 kb
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

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

int lazy[400], unde[nmax], sub[nmax], d[nmax], e, val[nmax], s[nmax];
unordered_map<int,int> fr[400];  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); bool fun = false;
    while(q--)
        {
            cin >> t >> a;
            if(t == 2)
                {
                    if(fun)
                        {
                            cout << "-1\n";
                            continue;
                        }

                    bool sem = 0;
                    for(int i = 0 ; i <= unde[n] && !sem ; i++)
                        {
                            if(!fr[i].count(a - lazy[i])) 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; if(fun) continue;
                    int st = s[a]; int dr = st + sub[a] - 1;
                    for(int i = unde[st] + 1; i < unde[dr]; i++)
                        lazy[i] += b;
                    for(int i = st; unde[i] == unde[st] && i <= dr; i++)
                        fr[unde[st]][lazy[unde[st]] + val[i]]--,
                        fr[unde[st]][lazy[unde[st]] + val[i]+b]++, val[i] += b;
                    if(unde[st] != unde[dr])
                        for(int i = B * unde[dr] + 1; i <= dr; i++)
                            fr[unde[dr]][lazy[unde[dr]] + val[i]]--,
                            fr[unde[dr]][lazy[unde[dr]] + val[i]+b]++, val[i] += b;
                }
        }
}