Submission #476647

#	Time	Username	Problem	Language	Result	Execution time	Memory
476647		Ozy	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	302 ms	50116 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 val second
#define ini first
#define fin second

struct x{
    lli a;
    lli b;
    lli ab;
    lli ba;
    lli aba;
    lli lazy;
};

lli n,q,w,a,b,c,offset,last,nuevo,in,fi,act;
lli euleriano[MAX*4],prof[MAX*4 ],aristas[MAX+2][3];
pair<lli,lli> rango[MAX+2];
vector<pair<lli,lli> > hijos[MAX+2];
x st[MAX*8];

void combina(lli nodo) {

    lli izq = nodo*2;
    lli der = (nodo*2)+1;

    st[nodo].a = max(st[izq].a, st[der].a);
    st[nodo].b = max(st[izq].b, st[der].b);

    st[nodo].ab = max({st[izq].ab, st[der].ab, (st[izq].a + st[der].b)});
    st[nodo].ba = max({st[izq].ba, st[der].ba, (st[izq].b + st[der].a)});

    st[nodo].aba = max({st[izq].aba, st[der].aba, (st[izq].ab + st[der].a), (st[izq].a + st[der].ba)});
}

void DFS(lli pos, lli padre, lli p) {

    prof[act] = p;
    euleriano[act] = pos;
    act++;

    for (auto h : hijos[pos]) {
        if (h.des == padre) continue;

        DFS(h.des,pos,p+h.val);

        prof[act] = p;
        euleriano[act] = pos;
        act++;
    }
}

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

        st[pos].a += st[pos].lazy;
        st[pos].b -= 2*st[pos].lazy;
        st[pos].ab -= st[pos].lazy;
        st[pos].ba -= st[pos].lazy;

        if (pos <= offset) {
            st[pos*2].lazy += st[pos].lazy;
            st[(pos*2)+1].lazy += st[pos].lazy;
        }

        st[pos].lazy = 0;
    }
}

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

    aplica(pos);

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

        lli mitad = (ini+fin)/2;
        actualiza(pos*2, ini, mitad, l, r, sum);
        actualiza((pos*2)+1, mitad+1, fin, l, r, sum);

        combina(pos);

    }

}

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

    cin >> n >> q >> w;
    rep(i,1,n-1) {

        cin >> a >> b >> c;
        aristas[i][0] = a;
        aristas[i][1] = b;
        aristas[i][2] = c;

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

    //llenar euleriano y profundidad
    act = 1;
    DFS(1,0,0);
    act--;
    //largo de ST es 1 - act
    rep(i,1,act) {
        rango[euleriano[i]].fin = i;
        if (rango[euleriano[i]].ini == 0) rango[euleriano[i]].ini = i;
    }

    offset = 1;
    while (offset < act) offset *= 2;
    offset--;

    rep(i,1,act) {
        st[offset+i].a = prof[i];
        st[offset+i].b = -(2*prof[i]);
        st[offset+i].ab = -prof[i];
        st[offset+i].ba = -prof[i];
        st[offset+i].aba = 0;
    }

    repa(i,offset,1) combina(i);

    last = 0;
    rep(i,1,q){
        cin >> a >> b;
        a = (a+last)%(n-1);
        a++;
        c = (b+last)%w;

        nuevo = c - aristas[a][2];
        aristas[a][2] = c;

        b = aristas[a][1];
        a = aristas[a][0];

        in = max(rango[a].ini, rango[b].ini);
        fi = min(rango[a].fin, rango[b].fin);

        actualiza(1,1,offset+1,in,fi,nuevo);

        last = st[1].aba;
        cout << last << "\n";
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 27 / 27