Pagini recente » Cod sursa (job #1617868) | Cod sursa (job #1266566) | Cod sursa (job #2806891) | Cod sursa (job #2216366) | Cod sursa (job #2496707)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f ("inception.in");
ofstream g ("inception.out");
int const NM = 3e5 + 1;
int h [NM] , ans [NM];
bool comp (pair <int , int> x , pair <int , int> y){
return x . first > y . first;
}
struct node {
int x , y;
bool operator < (node r) const {
return x > r . x;
}
};
priority_queue <node , vector <node> , less <node> > q [NM];
vector <node> add [NM];
vector <int> v [NM];
int s;
void mrg (priority_queue <node , vector <node> , less <node> > &z , priority_queue <node , vector <node> , less <node> > &z1){
while (z1 . size ()){
z . push (z1 . top ());
z1 . pop ();
}
}
int ks [NM];
void solve (int o){
for(auto i : v [o]){
solve (i);
mrg (q [o] , q [i]);
s += ks [i];
}
if (! v [o] . size ()){
for(auto i : add [o]){
ans [o] += i . y;
ks [o] += i . y;
q [o] . push (i);
}
return ;
}
int p = h [o];
for(auto i : add [o]){
s += i . y;
q [o] . push (i);
}
ans [o] = ks [o] = s;
node u;
if (q [o] . size ())
u = q [o] . top ();
while (q [o] . size () && p + 1 == q [o] . top () . x){
s -= q [o] . top () . y;
q [o] . pop ();
}
return;
}
int main()
{
int n , q , k , comp = 1 , H = 0;
f >> n >> q >> k;
while (q --){
int t , id , i , j;
f >> t >> id >> i >> j;
if (t == 1){
h [++ comp] = 1 + h [id];
H = max (H , h [comp]);
v [id] . push_back (comp);
}
else{
add [id] . push_back ({i , j});
}
}
for(int i = 1 ; i <= comp ; ++ i)
h [i] = H - h [i];
solve (1);
while (k --){
int p;
f >> p;
g << ans [p] << ' ';
}
return 0;
}