Submission #557585

#	Time	Username	Problem	Language	Result	Execution time	Memory
557585		RaresFelix	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	5022 ms	18592 KiB

diameter

#include <bits/stdc++.h>
#define MN 100071
#define MK 19

using namespace std;
using ll = long long;
using ii = pair<int, int>;
int n, q, max_weight;
vector<int> L[MN];
map<pair<int, int>, int> W; /// if slow, you may try to make a map for each node

namespace LCA {
    const int MB = 3 * MN;
    int BIT[MB], tmr, In[MN], Out[MN], Niv[MN];
    pair<int, int> RMQ[MK][MB];
    int EulerTour[MN];

    void bit_up(int p, int v) {
        //printf("update bit la poz %d cu %d\n", p, v);
        while(p < MB) BIT[p] += v, p += p & (-p);
    }
    int bit_q_p(int p) {
        int re = 0;
        while(p) re += BIT[p], p -= p & -p;
        return re;
    }
    int bit_query(int st, int dr) {
        return bit_q_p(dr) - (st ? bit_q_p(st - 1) : 0);
    }


    void dfi(int u, int p, int niv) {
        In[u] = Out[u] = ++tmr;
        EulerTour[tmr] = u;
        Niv[u] = niv;
        bit_up(In[u], W[{u, p}]);
        for(auto it : L[u]) if(it != p) {
            dfi(it, u, niv + 1);
            Out[u] = ++tmr;
            EulerTour[tmr] = u;
        }
        if(In[u] == Out[u])
            EulerTour[Out[u] = ++tmr] = u;
        bit_up(Out[u], -W[{u, p}]);
    }
    void init() {
        dfi(1, 0, 0);
        for(int i = 1; i <= tmr; ++i)
            RMQ[0][i] = {Niv[EulerTour[i]], EulerTour[i]};
        for(int k = 1; k < MK; ++k)
            for(int i = 1; i <= tmr; ++i) if(i + (1 << k) - 1<= tmr){
                RMQ[k][i] = min(RMQ[k-1][i], RMQ[k-1][i + (1 << (k-1))]);
            }
    //    printf("Euler Tour: "); for(int i = 1; i <= tmr; ++i) printf("%d ", EulerTour[i]);
    //    printf("\n");
    //    for(int k = 0; k <= 5; ++k) {
    //        printf("RMQ %d: ", k); for(int i = 1; i <= n; ++i) printf("(%d, %d); ", RMQ[k][i].first, RMQ[k][i].second);
    //        printf("\n");
    //    }
    }
    inline pair<int, int> rmq_query(int st, int dr) {
        assert(st <= dr);
        int l = 31 - __builtin_clz(dr - st + 1);
        return min(RMQ[l][st], RMQ[l][dr - (1 << l) + 1]);
    }
    inline int lca(int u, int v) {
        return rmq_query(min(In[u], In[v]), max(Out[u], Out[v])).second;
    }
    inline int dist(int u) {
        return bit_q_p(In[u]);
    }
    inline int dist(int u, int v) {
        int l = lca(u, v);
        return dist(u) + dist(v) - 2 * dist(l);
    }

    inline void update(int u, int v, int w) {
        if(Niv[u] > Niv[v]) swap(u, v);
        bit_up(In[v], w - W[{u, v}]);
        bit_up(Out[v], W[{u, v}] - w);
    }
}

namespace CENTR {
    int Sz[MN], croot, Cpar[MN];
    bool Used[MN];
    void dfi(int u, int p) {
        Sz[u] = 1;
        for(auto it : L[u])
            if(!Used[it] && it != p)
                dfi(it, u), Sz[u] += Sz[it];
    }
    int find_c(int u, int p, const int &bsz) {
        for(auto it : L[u])
            if(!Used[it] && it != p && Sz[it] * 2 > bsz) return find_c(it, u, bsz);
        return u;
    }
    using sol = tuple<int, int, int>;
    set<sol> BO[MN]; /// perechi {dist, sursa, nod}
    map<int, int> DistSursa[MN];
    map<int, int> NodSursa[MN];
    void desc(int u, int cpar) {
        dfi(u, 0);
        int c = find_c(u, 0, Sz[u]);
        if(!cpar)
            croot = c;
        Used[c] = 1;
        Cpar[c] = cpar;
        for(auto it : L[c])
            if(!Used[it]) desc(it, c);
    }
    void afis(sol a) {
        printf("%d %d %d ", get<0>(a), get<1>(a), get<2>(a));
    }
    inline pair<sol, sol> best(int u) {
        ///imi extrage 2 solutii din u(daca exista) promitatoare
        printf("Best sol pt %d : ", u);
        if(BO[u].empty()) {
            printf("gol\n");
            return {{0, 0, 0}, {0, 0, 0}};
        } 
        auto it = BO[u].rbegin();
        if(BO[u].size() == 1) {
            afis(*it); 
            printf("\n");
            return {*it, {0, 0, 0}};
        }
        sol a = *it, b; ++it; b = *it;
        afis(a), afis(b);
        printf("\n");
        return {a, b};
    }
    inline void remove(int u, int l) {
        if(!DistSursa[u].count(l)) return;
        sol prev = {DistSursa[u][l], l, NodSursa[u][l]};
        DistSursa[u].erase(l);
        NodSursa[u].erase(l);
        BO[u].erase(prev);
    }
    inline void add(int u, sol a) {
        auto &[d, l, v] = a;
        sol prev;
        if(DistSursa[u].count(l)) {
            prev = {DistSursa[u][l], l, NodSursa[u][l]};
        } else prev = {0, 0, 0};
        if(a > prev) {
            DistSursa[u][l] = d;
            NodSursa[u][l] = v;
            BO[u].erase(prev);
            BO[u].insert(a);
        }
    }
    void update(int u) {
        int last_source = u, u0 = u;
        u = Cpar[u];
        while(u) {
            remove(u, last_source);
            auto [a1, a2] = best(last_source);
            sol a3 = {LCA::dist(last_source, u), last_source, last_source};
            get<1>(a1) = get<1>(a2) = last_source;
            get<0>(a1) = LCA::dist(get<2>(a1), u);
            get<0>(a2) = LCA::dist(get<2>(a2), u); 
            add(u, a1);
            add(u, a2);
            add(u, a3);

            last_source = u;
            u = Cpar[u];
        }
    }
    void init() {
        desc(1, 0);
        for(int i = 1; i <= n; ++i)
            update(i);
    }
}
ii E[MN];
int main() {
    cin >> n >> q >> max_weight;
    for(int i = 1, u, v, w; i < n; ++i) {
        cin >> u >> v >> w;
        E[i] = {u, v};
        L[u].push_back(v), L[v].push_back(u);
        W[{u, v}] = W[{v, u}] = w;
    }
    LCA::init();
    CENTR::init();
    printf("radacina este %d\n", CENTR::croot);
    printf("--------------------------\n");
    int last = 0;
    for(int i = 1; i <= q; ++i) {
        int id, w;
        cin >> id >> w;
        id = (id + last) % (n - 1) + 1;
        w = (w + last) % max_weight;
        auto &[u, v] = E[id];
        LCA::update(u, v, w);
        CENTR::update(u);
        CENTR::update(v);
        auto [b1, b2] = CENTR::best(CENTR::croot);
        cout << (last = (get<0>(b1) + get<0>(b2))) << "\n";
    }
//    int op, u, v, w;
//    while(cin >> op >> u >> v) {
//        if(op == 1) {
//            cin >> w;
//            LCA::update(u, v, w);
//        } else {
//            printf("Pt cele doua nod lca-ul este %d si dist %d\n", LCA::lca(u, v), LCA::dist(u, v));
//        }
//    }
    return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'void CENTR::update(int)':
diameter.cpp:154:30: warning: unused variable 'u0' [-Wunused-variable]
  154 |         int last_source = u, u0 = u;
      |                              ^~

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