oj.uz

Submission #834816

# Submission time Handle Problem Language Result Execution time Memory
834816 2023-08-22T20:21:28 Z Ozy Designated Cities (JOI19_designated_cities) C++17
23 / 100
 603 ms 524288 KB 
#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];
pll 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};

    //debugsl(pos);
    //debug(dis);

    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;
    
    h_op[pos] = {0,pos};
    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].first + h.w;
        if(a > h_op[pos].first) h_op[pos] = {a,h_op[h.des].id};

        if (a > mejores[0].val) {
            swap(mejores[0],mejores[1]);
            mejores[0] = {a,h_op[h.des].id};
        }
        else if (a > mejores[1].val) mejores[1] = {a,h_op[h.des].id};
    }

    a = carga + sub[pos];
    a += mejores[0].val + mejores[1].val;
    
    if (a > op2) {
        raiz2 = mejores[0].id;
        op2 = a;

        //debugsl(mejores[0].id);
        //debug(mejores[1].id);
    }
}
    
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;
    
    //debug(act.id);
    
    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

    //debug(raiz2);
    //debug(total-op2);

    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

Compilation message

designated_cities.cpp: In function 'void busca_raiz(long long int, long long int, long long int)':
designated_cities.cpp:75:9: warning: unused variable 'act' [-Wunused-variable]
   75 |     lli act = 0;
      |         ^~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:208:15: 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]
  208 |         if (a >= res.size()) cout << res[res.size()-1] << "\n";
      |             ~~^~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 2 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Runtime error 603 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Runtime error 576 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 2 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 4 ms 5460 KB Output is correct
14 Correct 4 ms 5712 KB Output is correct
15 Correct 4 ms 5460 KB Output is correct
16 Correct 5 ms 5480 KB Output is correct
17 Correct 5 ms 5460 KB Output is correct
18 Correct 4 ms 5460 KB Output is correct
19 Correct 4 ms 5460 KB Output is correct
20 Correct 4 ms 5460 KB Output is correct
21 Correct 4 ms 5460 KB Output is correct
22 Correct 5 ms 5460 KB Output is correct
23 Correct 5 ms 5584 KB Output is correct
24 Correct 4 ms 5460 KB Output is correct
25 Correct 4 ms 5588 KB Output is correct
26 Correct 4 ms 5584 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Runtime error 603 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 2 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Runtime error 603 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -