oj.uz

Submission #475333

# Submission time Handle Problem Language Result Execution time Memory
475333 2021-09-21T22:54:55 Z Ozy Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 372 ms 27644 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#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 debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 100000
#define des first
#define p second

struct x{
    lli mayor;
    lli lazy;
    lli hder;
    lli hizq;
};

lli n,q,w,a,b,c,k,last,id,act,ult,sum,l,r;
lli peso[MAX+2];
pair<lli,lli> arr[MAX+2];

vector<pair<lli,lli> > hijos[MAX+2];
vector<lli> iniciales;
pair<lli,lli> rango[MAX+2];

vector<x> st;
multiset<lli> res;
multiset<lli>::iterator it;
lli valores[MAX+2],pertenece[MAX+2];

void recorre(lli pos, lli padre,lli prof) {

    rango[pos].first = act;
    if (padre == 1) pertenece[pos] = pos;
    else pertenece[pos] = pertenece[padre];

    bool tiene = false;
    for (auto h : hijos[pos]) {
        if (h.des == padre) continue;
        tiene = true;
        recorre(h.des,pos,prof + h.p);
    }

    if (!tiene) {
        act++;
        iniciales.push_back(prof);
    }
    rango[pos].second = act-1;

}

void arma(lli ini, lli fin, lli pos) {

    lli mitad;

    if (ini == fin) st[pos].mayor = iniciales[ini];
    else {

        mitad = (ini+fin)/2;
        st.push_back({0,0,0,0});
        st.push_back({0,0,0,0});

        st[pos].hizq = ult;
        st[pos].hder = ult+1;
        ult += 2;

        arma(ini,mitad,st[pos].hizq);
        arma(mitad+1,fin,st[pos].hder);

        st[pos].mayor = max(st[ st[pos].hizq ].mayor, st[ st[pos].hder ].mayor);
    }
}

void aplica(lli pos) {
    if (st[pos].lazy != 0) {

        if (st[pos].hizq != 0) {
            st[ st[pos].hizq ].lazy += st[pos].lazy;
            st[ st[pos].hder ].lazy += st[pos].lazy;
        }

        st[pos].mayor += st[pos].lazy;
        st[pos].lazy = 0;

    }
}

void actualiza(lli pos, lli ini, lli fin, lli l, lli r, lli val) {

    aplica(pos);

    if (ini >= l && fin <= r) {
        st[pos].lazy += val;
        aplica(pos);
    }
    else if (fin < l || ini > r) return ;
    else {

        lli mitad = (ini+fin)/2;
        actualiza(st[pos].hizq,ini,mitad,l,r,val);
        actualiza(st[pos].hder,mitad+1,fin,l,r,val);

        st[pos].mayor = max(st[ st[pos].hizq ].mayor, st[ st[pos].hder ].mayor);
    }
}

lli query(lli pos, lli ini, lli fin, lli l, lli r) {

    aplica(pos);
    if (ini >= l && fin <= r) return st[pos].mayor;
    else if (ini > r || fin < l) return 0;
    else {
        lli mitad = (ini+fin)/2;
        lli a = query(st[pos].hizq, ini,mitad,l,r);
        lli b = query(st[pos].hder, mitad+1,fin,l,r);
        return max(a,b);
    }

}

lli imprime() {

    if (res.size() == 1) {
        it = res.begin();
        return *it;
    }
    else {
        lli total;

        auto itr = res.rbegin();
        total = *itr;
        itr++;
        total += *itr;

        return total;
    }

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q >> w;
    rep(i,1,n-1) {
        cin >> a >> b >> c;
        arr[i] = {a,b};
        peso[i] = c;

        hijos[a].push_back({b,c});
        hijos[b].push_back({a,c});
    }

    act = 1;
    iniciales.push_back(0);

    recorre(1,0,0);
    act--;

    st.push_back({0,0,0,0});
    ult = 1;
    arma(1,act,0);
    for (auto h : hijos[1]) {
        valores[h.des] = query(0,1,act,rango[h.des].first,rango[h.des].second);
        res.insert(valores[h.des]);
    }

    rep(i,1,q) {

        //correcto
        cin >> id >> c;
        id += last;
        id %= (n-1);
        id++;
        c += last;
        c %= w;

        a = arr[id].first;
        b = arr[id].second;

        //fill

        sum = c - peso[id];
        peso[id] = c;
        l = max(rango[a].first, rango[b].first);
        r = min(rango[a].second, rango[b].second);

        if (pertenece[a] != 0) k = pertenece[a];
        else k = pertenece[b];
        it = res.lower_bound(valores[k]);
        res.erase(it);

        actualiza(0,1,act,l,r,sum);

        valores[k] = query(0,1,act,rango[k].first,rango[k].second);
        res.insert(valores[k]);

        //last = resultado
        last = imprime();
        cout << last << "\n";
    }
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2700 KB Output is correct
4 Correct 13 ms 2820 KB Output is correct
5 Correct 58 ms 3716 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 4 ms 2764 KB Output is correct
10 Correct 19 ms 3024 KB Output is correct
11 Correct 85 ms 4036 KB Output is correct
12 Correct 6 ms 3912 KB Output is correct
13 Correct 6 ms 3856 KB Output is correct
14 Correct 9 ms 3848 KB Output is correct
15 Correct 28 ms 4128 KB Output is correct
16 Correct 117 ms 5232 KB Output is correct
17 Correct 119 ms 25804 KB Output is correct
18 Correct 115 ms 25760 KB Output is correct
19 Correct 119 ms 25760 KB Output is correct
20 Correct 162 ms 26084 KB Output is correct
21 Correct 372 ms 27412 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 17184 KB Output is correct
2 Correct 241 ms 21240 KB Output is correct
3 Correct 238 ms 21292 KB Output is correct
4 Correct 260 ms 22356 KB Output is correct
5 Correct 267 ms 22692 KB Output is correct
6 Correct 309 ms 26072 KB Output is correct
7 Correct 212 ms 23152 KB Output is correct
8 Correct 234 ms 23180 KB Output is correct
9 Correct 271 ms 23216 KB Output is correct
10 Correct 288 ms 23896 KB Output is correct
11 Correct 286 ms 24620 KB Output is correct
12 Correct 306 ms 27260 KB Output is correct
13 Correct 145 ms 24340 KB Output is correct
14 Correct 152 ms 24376 KB Output is correct
15 Correct 153 ms 24432 KB Output is correct
16 Correct 180 ms 25324 KB Output is correct
17 Correct 204 ms 25756 KB Output is correct
18 Correct 231 ms 27644 KB Output is correct
19 Correct 135 ms 24400 KB Output is correct
20 Correct 139 ms 24524 KB Output is correct
21 Correct 145 ms 24520 KB Output is correct
22 Correct 181 ms 25272 KB Output is correct
23 Correct 202 ms 25656 KB Output is correct
24 Correct 226 ms 27600 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -