Cod sursa(job #2396717)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 3 aprilie 2019 19:26:43
Problema Arbore Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.59 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <cmath>
#define DIMN 100010
#define DIM 2000002
#define DIM_BUCKET 400
using namespace std;

ifstream in ("arbore.in");
ofstream out ("arbore.out");
vector <int> L[DIMN];
bitset <DIM> f[DIM_BUCKET];
int add[DIMN],a[DIMN],viz[DIMN],v[DIMN],st[DIM_BUCKET],dr[DIM_BUCKET],nrb[DIMN];
int n,m,c,p,s,i,bucket,start,fin,k,lg,x,y,ok,nr_buckets;
pair <int,int> poz[DIMN];
void dfs (int nod){
    viz[nod] = 1;
    v[++k] = nod;
    poz[nod].first = k;
    for (int i=0;i<L[nod].size();i++){
        int vecin = L[nod][i];
        if (!viz[vecin])
            dfs (vecin);
    }
    //v[++k] = nod;
    poz[nod].second = k;
}
/*void get_poz (int p){
    if (poz[p].first % lg != 0)
        start = (poz[p].first/lg)+1;
    else start = poz[p].first/lg;

    if (poz[p].second % lg != 0)
        fin = (poz[p].second/lg)-1;
    else fin = poz[p].second/lg;
}*/
int main (){

    in>>n>>m;
    for (i=1;i<n;i++){
        in>>x>>y;
        L[x].push_back (y);
        L[y].push_back (x);
    }

    dfs (1);

    lg = (int)sqrt(k);
    nr_buckets = k/lg;
    for (i=1;i<=k;i++){
        nrb[i] = i/lg; /// in ce bucket se afla un element
        if (i%lg != 0)
            nrb[i]++;
    }
    for (bucket=1;bucket<=nr_buckets;bucket++){
        st[bucket] = (bucket-1)*lg+1; /// unde incepe si unde se termina un bucket
        dr[bucket] = min (bucket*lg,k);
        f[bucket][0] = 1;
    }
    /// a[i] - cat am adunat la un nr care era in bucketurile incomplete
    /// add[i] - cat am adunat la bucketul complet i
    /// a[i]+add[nrb[i]] - valoarea care se afla de fapt in el i
    for (;m--;){
        in>>c;
        if (c == 1){
            in>>p>>s;
            x = poz[p].first, y = poz[p].second;
            if (nrb[x] == nrb[y]){ /// intervalul meu e tot inclus intr un bucket
                for (i=st[nrb[x]];i<=dr[nrb[x]];i++)
                    f[nrb[x]][a[i]] = 0;
                for (i=x;i<=y;i++)
                    a[i] += s;
                for (i=st[nrb[x]];i<=dr[nrb[x]];i++)
                    f[nrb[x]][a[i]] = 1;

            } else {
                for (i=dr[nrb[x]]+1;nrb[i]!=nrb[y];i+=lg)
                    add[nrb[i]] += s; /// lazy ul

                for (i=st[nrb[x]];i<=dr[nrb[x]];i++)
                    f[nrb[x]][a[i]] = 0; /// mai intai le demarchez PE TOATE din intervalul bucketului din stanga
                for (i=x;i<=dr[nrb[x]];i++)
                    a[i] += s;
                for (i=st[nrb[x]];i<=dr[nrb[x]];i++)
                    f[nrb[x]][a[i]] = 1;

                /// acum fac acelasi lucru si pentru dreapta

                for (i=st[nrb[y]];i<=dr[nrb[y]];i++)
                    f[nrb[y]][a[i]] = 0;
                for (i=st[nrb[y]];i<=y;i++)
                    a[i] += s;
                for (i=st[nrb[y]];i<=dr[nrb[y]];i++)
                    f[nrb[y]][a[i]] = 1;
                //add[nrb[x]] = add[nrb[y]] = 0;
            }

        } else {
            in>>s;
            ok = 0;
            for (bucket=1;bucket<=nr_buckets;bucket++){
                ok = 0;
                if (s-add[bucket] >= 0 && f[bucket][s-add[bucket]]){
                    for (i=st[bucket];i<=dr[bucket];i++)
                        if (a[i]+add[bucket] == s){
                            out<<v[i]<<"\n";
                            ok = 1;
                            break;
                        }
                }
                if (ok) break;
            }
            if (!ok)
                out<<"-1\n";
        }
    }


    return 0;
}