Pagini recente » Cod sursa (job #1137926) | Cod sursa (job #489686) | Cod sursa (job #1509271) | Cod sursa (job #2949951) | Cod sursa (job #999262)
Cod sursa(job #999262)
#include <fstream>
#include <vector>
#include <bitset>
#include <utility>
#include <cmath>
typedef std::pair<int,int> Bucket;
const int MAX_N(100005);
const int MAX_BUCKET(317);
const int MAX_VALUE(1000005);
int n, m, Size;
std::vector<int> Graph [MAX_N];
std::bitset<MAX_VALUE> Mark [MAX_BUCKET];
Bucket v [MAX_BUCKET];
int Tree [MAX_N], Pos;
std::pair<int,int> Index [MAX_N];
int Add [MAX_BUCKET];
int Value [MAX_N];
bool Viz [MAX_N];
void TreeDecomposition (int node)
{
Viz[node] = true;
Tree[Pos] = node;
Index[node].first = Pos;
++Pos;
for (auto it : Graph[node])
if (!Viz[it])
TreeDecomposition(it);
Index[node].second = Pos - 1;
}
inline void Build (void)
{
int root(std::sqrt(n));
int i(0), j(root - 1);
while (true)
{
++Size;
v[Size].first = i;
v[Size].second = j;
Mark[Size][0] = true;
if (j == n - 1)
break;
i = j + 1;
j = std::min(j + root,n - 1);
}
}
inline void Update (int left, int right, int value)
{
for (int i(1) ; i <= Size ; ++i)
{
if (v[i].first > right)
break;
if (v[i].second < left)
continue;
if (left <= v[i].first && v[i].second <= right)
Add[i] += value;
else
{
for (int j(v[i].first), end(v[i].second) ; j <= end ; ++j)
{
Mark[i][Value[Tree[j]]] = false;
Value[Tree[j]] += Add[i] + (left <= j && j <= right ? value : 0);
}
Add[i] = 0;
for (int j(v[i].first), end(v[i].second) ; j <= end ; ++j)
Mark[i][Value[Tree[j]]] = true;
}
}
}
inline int Query (int value)
{
for (int i(1) ; i <= Size ; ++i)
if (Add[i] <= value && Mark[i][value - Add[i]])
{
for (int j(v[i].first), end(v[i].second) ; j <= end ; ++j)
if (Value[Tree[j]] + Add[i] == value)
return Tree[j];
}
return -1;
}
int main (void)
{
std::ifstream input("arbore.in");
std::ofstream output("arbore.out");
input >> n >> m;
for (int i(1), x, y ; i < n ; ++i)
{
input >> x >> y;
Graph[x].push_back(y);
Graph[y].push_back(x);
}
TreeDecomposition(1);
Build();
int t, x, y;
while (m)
{
input >> t;
if (t == 2)
{
input >> x;
output << Query(x) << '\n';
}
else
{
input >> x >> y;
Update(Index[x].first,Index[x].second,y);
}
--m;
}
input.close();
output.close();
return 0;
}