Cod sursa(job #1340375)

Utilizator dariusdariusMarian Darius dariusdarius Data 11 februarie 2015 19:43:28
Problema Arbore Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <cmath>

#include <algorithm>
#include <fstream>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
const int MAX_N = 100005;
const int MAX_K = 330;
struct Piece {
    int added;
    multimap<int, int> values;
} p[MAX_K];

vector<int> tree[MAX_N];
int n, k, depth[MAX_N];
int start[MAX_N];
int finish[MAX_N];
int sum[MAX_N];

void dfs(int node, int father = 0) {
    depth[++ k] = node;
    start[node] = k;
    for (vector<int> :: iterator it = tree[node].begin(); it != tree[node].end(); ++ it) {
        if (*it != father) {
            dfs(*it, node);
        }
    }
    finish[node] = k;
}

void manual_update(int index, int x, int y, int value) {
    int first = (index - 1) * k + 1;
    int last = min(index * k, n);
    p[index].values.clear();
    for (int i = first; i <= last; ++ i) {
        sum[i] += p[index].added;
        if (x <= i && i <= y) {
            sum[i] += value;
        }
        p[index].values.insert(make_pair(sum[i], i));
    }
    p[index].added = 0;
}

void update(int x, int y, int value) {
    int px = (x + k - 1) / k, py = y / k;
    manual_update(px, x, min(px * k, n), value);
    if (px != py) {
        manual_update(py, (py - 1) * k + 1, y, value);
    }
    for (int i = px + 1; i < py; ++ i) {
        p[i].added += value;
    }
}

int main() {
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    int m, x, y;
    fin >> n >> m;
    for (int i = 1; i < n; ++ i) {
        fin >> x >> y;
        tree[x].push_back(y);
        tree[y].push_back(x);
    }
    dfs(1);
    k = static_cast<int>(sqrt(1.0 * n));
    int pieces = n / k + (n % k != 0);
    for (int i = 1; i <= pieces; ++ i) {
        int first = (i - 1) * k + 1;
        int last = min(i * k, n);
        for (int j = first; j <= last; ++ j) {
            p[i].values.insert(make_pair(0, j));
        }
    }
    for (int i = 1; i <= m; ++ i) {
        int type;
        fin >> type;
        if (type == 1) {
            int node, value;
            fin >> node >> value;
            update(start[node], finish[node], value);
        } else {
            int value; int ok = -1;
            fin >> value;
            for (int i = 1; i <= pieces; ++ i) {
                if (p[i].values.count(value - p[i].added)) {
                    ok = depth[p[i].values.lower_bound(value - p[i].added)->second];
                }
            }
            fout << ok << "\n";
        }
    }
    return 0;
}