Cod sursa(job #2401191)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 9 aprilie 2019 14:50:50
Problema Arbore Scor 0
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 2.78 kb
#include <bits/stdc++.h>

#define Nmax 100005
#define Vmax 1000001
#define sqrtMax 318

using namespace std;

ifstream fin("arbore.in");
ofstream fout("arbore.out");

struct batog
{
    int le, ri;
    int V;
    bitset <Vmax> exists;
};

batog B[sqrtMax];

int N, M, L, numOfBlocks;
int SIZE;
vector <int> G[Nmax];
int add[Nmax];
int le[Nmax], ri[Nmax];
bool vis[Nmax];
int nodes[Nmax];

void DFS(int node)
{
    vis[node] = true;
    le[node] = ++L;
    nodes[L] = node;
    for(auto it : G[node])
        if(!vis[it])
            DFS(it);
    ri[node] = L;
}

void upE(int block, int t)
{
    for(int i = B[block].le; i <= B[block].ri; i++)
        B[block].exists[add[i]] = t;
}

void addInt(int le, int ri, int val)
{
    for(int i = le; i <= ri; i++)
        add[i] += val;
}

void update(int le, int ri, int val)
{
    for(int block = 1; block <= numOfBlocks; block++)
    {
        if(le <= B[block].le && B[block].ri <= ri)
            B[block].V += val;
        else
        {
            if(B[block].le <= le && ri <= B[block].ri)
            {
                upE(block, 0);
                addInt(le, ri, val);
                upE(block, 1);
            }
            else
            if(le >= B[block].le && le <= B[block].ri)
            {
                upE(block, 0);
                addInt(le, B[block].ri, val);
                upE(block, 1);
            }
            else
            if(ri <= B[block].ri && B[block].le <= ri)
            {
                upE(block, 0);
                addInt(B[block].le, ri, val);
                upE(block, 1);
            }
        }
    }
}

int query(int S)
{
    for(int block = 1; block <= numOfBlocks; block++)
        if(S >= B[block].V && B[block].exists[S - B[block].V] == 1)
            for(int i = B[block].le; i <= B[block].ri; i++)
                if(add[i] + B[block].V == S)
                {
                    cout << "TE FUT";
                    return nodes[i];
                }
    return -1;
}

int main()
{
    fin >> N >> M;
    SIZE = sqrt(N);
    do
    {
        ++numOfBlocks;
        B[numOfBlocks].le = B[numOfBlocks - 1].ri + 1;
        B[numOfBlocks].ri = B[numOfBlocks - 1].ri + SIZE;
        B[numOfBlocks].ri = min(B[numOfBlocks].ri, N);
        upE(numOfBlocks, 1);
    }while(B[numOfBlocks].ri != N);
    for(int i = 1; i < N; i++)
    {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    while(M--)
    {
        int t, P, S;
        fin >> t;
        if(t == 1)
        {
            fin >> P >> S;
            update(le[P], ri[P], S);
        }
        else
        {
            fin >> S;
            fout << query(S) << "\n";
        }
    }
    return 0;
}