Cod sursa(job #2072911)

Utilizator antanaAntonia Boca antana Data 22 noiembrie 2017 14:19:10
Problema Arbore Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.89 kb
#include <bits/stdc++.h>

using namespace std;

FILE *fin = fopen( "arbore.in", "r" );
FILE *fout= fopen( "arbore.out","w" );

const int BUF  = (1<<17);
const int maxv = 1e6 + 1;
const int maxn = 1e5 + 5;
const int Sqrt = 128;
const int buck = 1000;

char buf[BUF], buf2[BUF];
int pos = BUF, pos2;

inline char getChar() {
    if (pos == BUF)
        pos = 0, fread( buf, 1, BUF, fin );
    return buf[ pos++ ];
}

inline int getInt() {
    int nr = 0;
    char c = getChar();
    while (!isdigit(c))
        c = getChar();
    while (isdigit(c)) {
        nr = nr*10 + c-'0';
        c = getChar();
    }
    return nr;
}

inline void writeChar( char c ) {
    buf2[ pos2++ ] = c;
    if (pos2 == BUF)
        pos2 = 0, fwrite( buf2, 1, BUF, fout );
}

inline void writeInt( int nr ) {
    char s[ 15 ];
    int sg = 1, top = 0;
    if (nr < 0)
        sg = -1, nr *= -1;
    while (nr) {
        s[ top++ ] = nr%10 + '0';
        nr /= 10;
    }
    if (sg == -1)
        s[ top++ ] = '-';
    while (top) {
        top--;
        writeChar( s[ top ] );
    }
}

vector < int > G[maxn];
pair < int, int > Ends[maxn];
unordered_set < int > val[buck];

int n, m, k, v[maxn], values[maxn], where[maxn], lazy[buck];

void dfs( int node, int dad ) {
    v[ ++k ] = node;
    Ends[ node ].first = k;
    for (int son: G[ node ])
        if (son != dad)
            dfs( son, node );
    Ends[ node ].second = k;
}

inline void update( int x, int y, int value ) {
    if (where[ x ] == where[ y ]) {
        for (int i = x; i <= y; i++)
            values[ i ] += value;
        val[ where[ x ] ].clear();
        for (int i = (where[ x ] - 1) * Sqrt + 1; i <= where[ x ] * Sqrt; i++)
            val[ where[ x ] ].insert( values[ i ] );
        return;
    }

    for (int i = where[ x-1 ] + 1; i < where[ y+1 ]; i++)
        lazy[ i ] += value;

    pair <int, int> left, right;

    if (where[ x-1 ] == where[ x ]) {
        left = { x, min( y, where[ x ] * Sqrt ) };
        for (int i = left.first; i <= left.second; i++)
            values[ i ] += value;
        val[ where[ x ] ].clear();
        for (int i = left.first; i <= left.second; i++)
            val[ where[ x ] ].insert( values[ i ] );
    }


    if (where[ y ] == where[ y+1 ]) {
        right = { max( (where[ y ] - 1) * Sqrt + 1, x ), y };
        for (int i = right.first; i <= right.second; i++)
            values[ i ] += value;
        val[ where[ y ] ].clear();
        for (int i = right.first; i <= right.second; i++)
            val[ where[ y ] ].insert( values[ i ] );
    }
}

inline int searchBucket( int idx, int sum ) {
    for (int i = (idx - 1) * Sqrt + 1; i <= idx * Sqrt; i++)
        if (values[ i ] == sum)
            return v[ i ];
    return -1;
}

inline int query( int sum ) {
    for (int i = 1; (i-1) * Sqrt + 1 <= n; i++)
        if (val[ i ].find( sum - lazy[ i ] ) != val[ i ].end())
            return searchBucket( i, sum - lazy[ i ] );
    return -1;
}

int main()
{
    int op, x, y;

    n = getInt();
    m = getInt();

    for (int i = 1; i < n; i++) {
        x = getInt();
        y = getInt();
        G[ x ].push_back( y );
        G[ y ].push_back( x );
    }

    for (int i = 1; (i-1) * Sqrt + 1 <= n + 1; i++) {
        where[ (i-1) * Sqrt + 1 ] = i;
        val[ i ].insert( 0 );
    }

    for (int i = 1; i <= n + 1; i++)
        if (!where[ i ])
            where[ i ] = where[ i-1 ];

    dfs( 1, 0 );

    for (int i = 1; i <= m; i++) {
        op = getInt();
        if (op == 1) {
            x = getInt();
            y = getInt();
            update( Ends[ x ].first, Ends[ x ].second, y );
        }
        else {
            x = getInt();
            writeInt( query( x ) );
            writeChar( '\n' );
        }
    }

    if (pos2)
        fwrite( buf2, 1, pos2, fout );

    return 0;
}