Cod sursa(job #796211)

Utilizator danalex97Dan H Alexandru danalex97 Data 10 octombrie 2012 20:51:39
Problema Arbore Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <cmath>
using namespace std;

const int Nmax = 100010;
const int Sqv = 320;
const int Smax = 1000010;

vector<int> Leg[Nmax];

int N,M,Act,Sec,Nbr;
int Begin[Nmax];
int Norm[Nmax];
int End[Nmax];

int Dad[Nmax];

int A[Nmax];
int B[Sqv];
bitset<Smax> P[Sqv];

ifstream F("arbore.in");
ofstream G("arbore.out");

void Get(int Nod)
{
    ++Act;
    Begin[Nod]=Act;
    Norm[Act]=Nod;

    for (vector<int>::iterator it=Leg[Nod].begin();it!=Leg[Nod].end();++it)
        if ( *it != Dad[Nod] )
            Get( *it );

    End[Nod]=Act;
}

void Update(int st,int dr,int val)
{
    for (int i=1;i<=Nbr;++i)
    {
        int l = (i-1)*Sec+1;
        int r = min(i*Sec,N);
        if ( l >= st && r <= dr )
            B[i] += val;
        else
            if ( l <= st && r >= dr )
            {
                for ( int j=st;j<=dr;++j )
                {
                    A[j] += val;
                    P[i][A[j]] = 1;
                }
            }
            else
                if ( l <= st && r <= dr )
                {
                    for ( int j=st;j<=r;++j )
                    {
                        A[j] += val;
                        P[i][A[j]] = 1;
                    }
                }
                else if ( l >= st && r >= dr )
                {
                    for ( int j=l;j<=dr;++j )
                    {
                        A[j] += val;
                        P[i][A[j]] = 1;
                    }
                }
    }
}

void Query( int Sum )
{
    for (int i=1;i<Nbr;++i)
        if ( Sum-B[i]>=0  )
        if ( P[i][Sum-B[i]] || Sum-B[i] == 0 )
        {
            for (int j=1;j<=Sec;++j)
                if ( A[(i-1)*Sec+j]+B[i] == Sum )
                {
                    G<<Norm[(i-1)*Sec+j]<<'\n';
                    return;
                }
        }
    for (int j=(Nbr-1)*Sec+1;j<=N;++j)
        if ( Sum-B[Nbr]>=0  )
        if ( A[j]+B[Nbr] == Sum )
        {
            G<<Norm[j]<<'\n';
            return;
        }
    G<<-1<<'\n';
}

int main()
{
    F>>N>>M;
    for (int i=1,x,y;i<N;++i)
    {
        F>>x>>y;
        Leg[x].push_back( y );
        Leg[y].push_back( x );
        Dad[ y ]= x;
    }

    Get( 1 );
    Sec = (int) sqrt(double(N));
    Nbr = N/Sec + ( (N/Sec) *Sec < N );

    while ( M-- )
    {
        int type,a,b;
        F>>type;
        if ( type == 1 )
        {
            F>>a>>b;
            Update( Begin[a] , End[a] , b );
        }
        else
        {
            F>>a;
            Query( a );
        }
    }
}