Cod sursa(job #2616385)

Utilizator david.teacaDavid Stefan Teaca david.teaca Data 18 mai 2020 12:27:56
Problema Arbore Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <cmath>
 
using namespace std;
 
ifstream fin("arbore.in");
ofstream fout("arbore.out");
 
const int NMax = 1e5, XMax = 1e6, BMax = 400;
 
int N, K, M, V[NMax + 5], A[NMax + 5], First[NMax + 5], Last[NMax + 5], id;
vector <int> G[NMax + 5];
 
struct
{
    int st, dr, l;
    bitset <XMax + 5> X;
}
B[BMax + 5];
 
void DFS(int Nod, int Tata)
{
    First[Nod] = ++K;
    V[K] = Nod;
 
    for(auto Vecin : G[Nod])
        if(Vecin != Tata)
            DFS(Vecin, Nod);
 
    Last[Nod] = K;
}
 
void Update(int val, int i, int st, int dr)
{
    int stB = B[i].st, drB = B[i].dr;
 
    if(dr < stB || drB < st)
        return;
 
    if(st <= stB && drB <= dr)
    {
        B[i].l += val;
        return;
    }
 
    for(int j = max(stB, st); j <= min(drB, dr); j++)
    {
        B[i].X[A[j]] = 0;
        A[j] += val;
    }
 
    for(int j = stB; j <= drB; j++)
        B[i].X[A[j]] = 1;
}
 
int Query(int s)
{
    for(int i = 1, val; i <= K; i++)
    {
        val = s - B[i].l;
 
        if(val < 0) continue;
        if(B[i].X[val] == 0) continue;
 
        for(int j = B[i].st; j <= B[i].dr; j++)
            if(A[j] == val)
                return V[j];
    }
    return -1;
}
 
int main()
{
    fin >> N >> M;
 
    for(int i = 1, a, b; i < N; i++)
    {
        fin >> a >> b;
 
        G[a].push_back(b);
        G[b].push_back(a);
    }
    DFS(1, 0);
    int lung = sqrt(N); K = 0;
 
    for(int i = 1; i <= N; i += lung)
    {
        K++;
        B[K].st = i, B[K].dr = min(i + lung - 1, N);
        B[K].X[0] = 1;
    }
 
    for(int i = 1, t, p, s; i <= M; i++)
    {
        fin >> t;
 
        if(t == 1)
        {
            fin >> p >> s;
 
            for(int k = 1; k <= K; k++)
                Update(s, k, First[p], Last[p]);
        }
        else
        {
            fin >> s;
            fout << Query(s) << '\n';
        }
    }
    fin.close();
    fout.close();
 
    return 0;
}