Cod sursa(job #2496707)

Utilizator DordeDorde Matei Dorde Data 21 noiembrie 2019 15:59:49
Problema A+B Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 kb
#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;
}