Submission #475332

#	Time	Username	Problem	Language	Result	Execution time	Memory
475332		Ozy	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	199 ms	17304 KiB

diameter

#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];
        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
• Subtask 2: 0 / 13
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27