제출 #834802

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
834802		Ozy	Designated Cities (JOI19_designated_cities)	C++17	0 / 100	606 ms	524288 KiB

designated_cities

    #include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,b) for(int i = (a); i <= (b); i++)
    #define repa(i,a,b) for(int i = (a); i >= (b); i--)
    #define lli long long int
    #define debug(a) cout << #a << " = " << a << endl
    #define debugsl(a) cout << #a << " = " << a << ", "
    #define pll pair<lli,lli>
     
    #define MAX 200000
    //para el vector de stree
    #define val first 
    #define id second
     
    struct x {
        lli des;
        lli w;
        lli comp;
    };
     
    lli n,a,b,c,d,raiz,op,total,q,raiz2,op2;
    vector<x> hijos[MAX+2];
    lli sub[MAX+2],h_op[MAX+2];
    vector<lli> res;
    //para el euler y el stree
    lli papa[MAX+2],vis[MAX+2],offset,cont,aport[MAX+2],lazy[MAX+2];
    pll stree[MAX*4],euler[MAX+2];    
     
    void push(lli pos) {
        if (lazy[pos] == 0) return;
        stree[pos].val -= lazy[pos];
        if(pos < offset) {
            lazy[pos*2] += lazy[pos];
            lazy[pos*2+1] += lazy[pos];
        }
        lazy[pos] = 0;
    }
     
    void pre_dfs(lli pos, lli padre) {
        for(auto h : hijos[pos]) {
            if(h.des == padre) continue;
            pre_dfs(h.des,pos);
            sub[pos] += sub[h.des] + (h.comp-h.w);
        }
    }
     
    void def_euler(lli pos, lli padre, lli dis) { // me va a dar tle, necesito un vector donde guarde su aportacion
        euler[pos].first = cont++;
        stree[ euler[pos].first +offset-1] = {dis,pos};
        papa[pos] = padre;
        for(auto h : hijos[pos]){
            if(h.des == padre) continue;
            aport[h.des] = h.w;
            def_euler(h.des,pos,dis+h.w);
        }
        euler[pos].second = cont;
    }
     
    void busca_raiz(lli pos, lli padre,lli carga) {
     
        lli a = carga + sub[pos];
        if (a > op){
            op = a;
            raiz = pos;
        }  
     
        pll mejores[2];
        mejores[0].val = 0;
        mejores[1].val = 0;
        lli act = 0;
     
        for(auto h : hijos[pos]){
            if(h.des == padre) continue;
            a = carga + sub[pos] - sub[h.des];
            a -= (h.comp-h.w);
            a += h.w;
            busca_raiz(h.des,pos,a);
     
            a = h_op[h.des] + h.w;
            h_op[pos] = max(h_op[pos],a);
            if (a > mejores[0].val) {
                swap(mejores[0],mejores[1]);
                mejores[0] = {a,h.des};
            }
            else if (a > mejores[1].val) mejores[1] = {a,h.des};
        }
     
        a = carga + sub[pos];
        a += mejores[0].val + mejores[1].val;
     
        if (a > op2) {
            raiz2 = mejores[0].id;
            op2 = a;
        }
    }
     
    void update(lli pos, lli ini, lli fin, lli l, lli r, lli v) {
        push(pos);
     
        if (ini > r || fin < l) return;
        if (l <= ini && fin <= r) {
            lazy[pos] = v;
            push(pos);
            return;
        }
     
        lli mitad = (ini+fin)/2;
        update(pos*2,ini,mitad,l,r,v);
        update(pos*2+1,mitad+1,fin,l,r,v);
     
        stree[pos] = max(stree[pos*2],stree[pos*2+1]);
    }
     
    void solve() {
        pll act = stree[1];
        op += act.val;
     
        if(act.val == 0) return;
     
        lli pos = act.id;
        while (vis[pos] == 0) {
     
            //debugsl(act.val);
            //debug(act.id);
            //debugsl(euler[pos].first);  
            //debugsl(euler[pos].second-1);
            //debug(aport[pos]);
     
            vis[pos] = 1;
            update(1,1,offset,euler[pos].first, euler[pos].second-1,aport[pos]);
            pos = papa[pos];
        }
    }
     
    void cambia_op(lli pos, lli padre) {
        for(auto h : hijos[pos]) {
            if (h.des == padre) continue;
            op += h.comp - h.w;
            cambia_op(h.des,pos);
        }
    }
     
    int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
     
        cin >> n;
        rep(i,1,n-1) {
            cin >> a >> b >> c >> d;
            hijos[a].push_back({b,c,c+d});
            hijos[b].push_back({a,d,c+d});
            total += (c+d);
        }
     
        pre_dfs(1,0);
        busca_raiz(1,0,0);
        //funciona
        res.push_back(total-op);
     
        //ahora tengo que construir el nuevo arbol con el camino euleriano
        //sobre el irme acabando las hojas con la mayor distancia a la raiz/algun camino previo
        //hacer greedy y al final responder
        offset = 1;
        while (offset < n) offset *= 2;
        cont = 1;
     
        op = 0;
        cambia_op(raiz2,0);
        def_euler(raiz2,0,0);
        repa(pos ,offset-1,1) stree[pos] = max(stree[pos*2], stree[(pos*2)+1]);
     
        //debug(raiz2);
        //rep(i,1,offset*2) push(i);
        //rep(i,0,n-1) {debugsl(stree[offset+i].val); debug(stree[offset+i].id);}
        //cout << endl;
     
        while(stree[1].val > 0) {
            solve();
            res.push_back(total-op);
            //rep(i,1,offset*2) push(i);
            //rep(i,0,n-1) {debugsl(stree[offset+i].val); debug(stree[offset+i].id);}
            //cout << endl;
        }
     
        //for(auto act : res) debug(act);
     
        cin >> q;
        rep(i,1,q) {
            cin >> a;
            a--;
            if (a >= res.size()) cout << res[res.size()-1] << "\n";
            else cout << res[a] << "\n";
        }
        return 0;  
    }
    //que no se me ovlide agarrar 2 hojas en la primera pasada (que pasa si no hay 2 hojas)
    //las respuestas van uno reccorrido hacia la derecha, entonces checar
    //checar que todas las cosas que lo necesiten lleven la funcion de push

컴파일 시 표준 에러 (stderr) 메시지

designated_cities.cpp: In function 'void busca_raiz(long long int, long long int, long long int)':
designated_cities.cpp:70:13: warning: unused variable 'act' [-Wunused-variable]
   70 |         lli act = 0;
      |             ^~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:191:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |             if (a >= res.size()) cout << res[res.size()-1] << "\n";
      |                 ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44