Pagini recente » Borderou de evaluare (job #2098704) | Atasamentele paginii Profil Bidek921 | Borderou de evaluare (job #1781800) | Cod sursa (job #1223009)
#include <fstream>
#include <cmath>
#include <vector>
using namespace std;
const int NMAX = 100002;
vector < int > Tree[NMAX];
int Node[NMAX], st[NMAX], c[NMAX], inf[320], val[NMAX], b[NMAX], nr, SQRT, n, m, ind, First[NMAX], Last[NMAX];
int viz[NMAX],a[320][NMAX];
ofstream g("arbore.out");
inline void Update(int x,int y,int s)
{
int b1 = b[x];
//g<<"x = "<<x<<" y = "<<y<<" s = "<<s<<"\n";
while(x <= y && c[x] == 0)
{
//g<<"Delete "<<val[x]<<" position : "<<x<<"\n";
//g<<"Add "<<val[x]+s<<" position : "<<x<<"\n";
a[b1][val[x]]--;
a[b1][val[x]+s]++;
val[x] += s;
x++;
}
b1 = b[x];
if(x > y)
return ;
int b2 = b[y];
while(c[y] == 0)
{
//g<<"Delete "<<val[y]<<" position : "<<y<<"\n";
//g<<"Add "<<val[y]+s<<" position : "<<y<<"\n";
a[b2][val[y]]--;
a[b2][val[y]+s]++;
val[y] += s;
--y;
}
//g<<"Delete "<<val[y]<<" position : "<<y<<"\n";
//g<<"Add "<<val[y]+s<<" position : "<<y<<"\n";
a[b2][val[y]]--;
a[b2][val[y]+s]++;
val[y] += s;
--y;
b2 `= b[y];
for( ; b1 <= b2; ++b1){
inf[b1] += s;
//g<<"Add "<<s<<" bucket "<<b1<<"\n";
}
}
inline int Solve(const int s)
{
for(int i = 1;i <= nr; ++i)
{
int x = s - inf[i];
if(x < 0)
continue ;
if(a[i][x]>0){
// g<<"Found at bucket "<<i<<" ";
for(x = st[i]; val[x] + inf[i] != s; ++x);
// g<<"and position "<<x<<"\n";
return Node[x];
//return 1;
}
}
return -1;
}
inline void DFS(const int node)
{
viz[node] = 1;
++ind;
First[node] = ind;
Node[ind] = node;
for(vector < int > ::iterator it = Tree[node].begin() ; it != Tree[node].end() ; ++it)
if(!viz[*it])
DFS(*it);
Last[node] = ind;
}
int main(){
ifstream f("arbore.in");
f >> n >> m;
SQRT = sqrt(n);
for(int i = 1;i < n; ++i)
{
int x, y;
f >> x >> y;
Tree[x].push_back(y);
Tree[y].push_back(x);
}
DFS(1);
nr = 1;
int r = 0;
c[1] = 1;
st[nr] = 1;
//g<<1<<"\n";
for(int i = 1;i <= n; ++i)
{
//g<<Node[i]<<" ";
++r;
if(r==SQRT+1){
r = 1;
++nr;
//g<<i<<"\n";
c[i] = 1;
st[nr] = i;
}
b[i] = nr;
++a[nr][0];
}
//g<<"\n";
//g<<nr<<"\n";
while(m--)
{
int op,x,s;
f >> op;
if(op==1)
{
f >> x >> s;
//g<<x<<" first = "<<First[x]<<" last = "<<Last[x]<<"\n";
Update(First[x],Last[x],s);
}
else{
f >> s;
g<<Solve(s)<<"\n";
}
}
f.close();
g.close();
return 0;
}