Cod sursa(job #1722168)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 27 iunie 2016 15:03:48
Problema Arbore Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include<cstdio>
#include<vector>
#include<bitset>
#define SIZE 330
#define MAXN 100010
using namespace std;
vector<int> g[MAXN];
bitset<MAXN> possible[SIZE+5];
int n,m,first[MAXN],last[MAXN],order[MAXN],current=0;
int add[MAXN],v[MAXN];
void DFS(int node,int father){
    int i;
    current++;
    order[current]=node;
    first[node]=current;
    for(i=0;i<g[node].size();i++)
        if(g[node][i]!=father)
            DFS(g[node][i],node);
    last[node]=current;
}
void Update(int left,int right,int value){
    int bucket,i;
    bucket=(left-1)/SIZE+1;
    for(i=(bucket-1)*SIZE+1;i<=right&&i<=bucket*SIZE;i++)
        possible[bucket][v[i]]=0;
    for(i=left;i<=right&&i<=bucket*SIZE;i++)
        v[i]+=value;
    for(i=(bucket-1)*SIZE+1;i<=bucket*SIZE;i++)
        possible[bucket][v[i]]=1;
    if(bucket==right/SIZE+1)
        return;
    bucket++;
    if(bucket!=right/SIZE)
        for(bucket;bucket*SIZE<=right;bucket++)
            add[bucket]+=value;
    for(i=(bucket-1)*SIZE+1;i<=bucket*SIZE;i++)
        possible[bucket][v[i]]=0;
    for(i=(bucket-1)*SIZE+1;i<=right&&i<bucket*SIZE;i++)
        v[i]+=value;
    for(i=(bucket-1)*SIZE+1;i<=bucket*SIZE;i++)
        possible[bucket][v[i]]=1;
}
int Query(int value){
    int bucket,i;
    for(bucket=1;bucket*SIZE<=n;bucket++)
        if(value>=add[bucket]&&possible[bucket][value-add[bucket]])
            for(i=(bucket-1)*SIZE+1;i<=bucket*SIZE;i++)
                if(v[i]+add[bucket]==value)
                    return order[i];
    for(i=(bucket-1)*SIZE+1;i<=n;i++)
        if(v[i]+add[bucket]==value)
            return order[i];
    return -1;
}
int main(){
    freopen("arbore.in","r",stdin);
    freopen("arbore.out","w",stdout);
    int i,a,b,type,p,s;
    scanf("%d%d",&n,&m);
    for(i=1;i<n;i++){
        scanf("%d%d",&a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    DFS(1,0);
    for(i=1;i<=m;i++){
        scanf("%d",&type);
        if(type==1){
            scanf("%d%d",&p,&s);
            Update(first[p],last[p],s);
        }
        else{
            scanf("%d",&s);
            printf("%d\n",Query(s));
        }
    }
    return 0;
}