Cod sursa(job #2398168)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 5 aprilie 2019 09:33:17
Problema Arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.2 kb
#include <cstdio>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cmath>

#define DIMN 100001
#define RADICAL 400
using namespace std;
int f[DIMN],inc[DIMN],sf[DIMN],desf[DIMN],b_nod[DIMN],a[DIMN],add[RADICAL];
vector <int> v[DIMN];
pair <int,int> buck[RADICAL];
int k = 0;
bitset <1000001> apar[RADICAL];
void dfs (int nod){
    int i,vecin;
    f[nod]=1;
    inc[nod]=k+1;
    desf[++k]=nod;
    for (i=0;i<v[nod].size();i++){
        vecin=v[nod][i];
        if (!f[vecin]){
            dfs (vecin);
        }
    }
    sf[nod]=k; /// intre [ inc .. sf ] e subarborele
}
int main()
{
    FILE *fin=fopen ("arbore.in","r");
    FILE *fout=fopen ("arbore.out","w");
    int n,m,x,y,rad,elem,i,j,cer,fr,sc,bi;
    fscanf (fin,"%d%d",&n,&m);
    for (i=1;i<n;i++){
        fscanf (fin,"%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs (1);
    rad = sqrt (n);
    elem=1;
    buck[elem].first=1;
    b_nod[1] = 1;
    for (i=1;i<=n;i++){
        b_nod[i] = elem;
        if ( i % rad == 0 ){
            buck[elem].second = i;
            elem++;
            buck[elem].first = i + 1;
        }
    }
    buck[elem].second = n;
    /// in buck am toate bucketurile de care am nevoie
    /// b_nod[i] = bucketul in care se afla i
    /// add [bucket] = val pe care o adaugi la tot bucketul bucket
    /// a[i] = val pe care o adaugi in elem i dar nu pe tot bucketul lui i
    for (;m;m--){
        fscanf (fin,"%d",&cer);
        if (cer==1){ /// update
            fscanf (fin,"%d%d",&x,&y);
            fr= inc[x];
            sc= sf[x];
            bi = b_nod[x];
            if (buck[b_nod[x]].first < fr){ /// nu incepe fix unde trb
                for (i=fr;i<=buck[b_nod[x]].second; i++ ) /// bucket umplut pe jum
                    a[i] += y;
                apar[b_nod[x]].reset(); /// modifici a - ul bucketului
                for (i=buck[b_nod[x]].first ; i<=buck[b_nod[x]].second ;i++){
                    apar[b_nod[x]][a[i]] = 1;
                }
                bi = b_nod[x] + 1;
            }
            for (i=bi; buck[i].second<=sc ; i ++){
                add[i] += y; /// adaugi la tot bucketul asta y
            }
            if (buck[i].first<=sc){ /// bucket de sf ne umplut in totalitate
                bi=i;
                for (i = buck[bi].first ; i <= sc ; i++)
                    a[i] += y;
                apar[bi].reset(); /// modifici a - ul bucketului astuia
                for (i=buck[bi].first ; i<=buck[bi].second ;i++){
                    apar[bi][a[i]] = 1;
                }
            }

        }
        else { /// query
            fscanf (fin,"%d",&x);
            for (i=1;i<=elem;i++){
                if ( x- add[i] >=0 && apar[i][ x - add[i] ]){
                    for (j = buck[i].first ; j<= buck[i].second ; j ++){
                        if (a[j] + add[i] == x){
                            fprintf (fout,"%d\n",desf[j]);
                            break;
                        }
                    }
                    break;
                }
            }
            if (i>elem)
                fprintf (fout,"-1\n");
        }
    }
    return 0;
}