Submission #557586

#	Time	Username	Problem	Language	Result	Execution time	Memory
557586		RaresFelix	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	1649 ms	159984 KiB

diameter

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

using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
ll n, q, max_weight;
vector<ii> L[MN];
namespace AINT {
    /// A shared data structure between centroids for best 2 numbers in interval
    ll V[2][4 * MN], Lazy[4 * MN], len;

    void init(int l0) {
        len = l0;
        for(int i = 1; i <= 4 * len; ++i)
            V[1][i] = -(1ll << 60);
    }

    inline void prop(ll u, ll s, ll d) {
        if(!Lazy[u]) return;
        V[0][u] += Lazy[u], V[1][u] += Lazy[u];
        if(s != d) {
            Lazy[u << 1] += Lazy[u];
            Lazy[u << 1 | 1] += Lazy[u];
        }
        Lazy[u] = 0;
    }

    void add(ll l, ll r, ll v, ll u = 1, ll s = 1, ll d = len) {
        if(d < l || r < s) return;
        prop(u, s, d);
        if(l <= s && d <= r) {
            Lazy[u] += v;
            prop(u, s, d);
            //printf("    Dupa un add la %d(%d, %d) am modificat maximele la %d si %d\n", u, s, d, V[0][u], V[1][u]);
            return;
        }
        add(l, r, v, u << 1, s, (s + d) >> 1);
        add(l, r, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
        ll p1 = 0, p2 = 0;
        for(ll p = 0; p < 2; ++p) {
            if(V[p1][u << 1] > V[p2][u << 1 | 1]) V[p][u] = V[p1++][u << 1];
            else V[p][u] = V[p2++][u << 1 | 1];
        }
        //printf("    Dupa un add la %d(%d, %d) am modificat maximele la %d si %d\n", u, s, d, V[0][u], V[1][u]);
    }
    
    pair<ll, ll> query(ll l, ll r, ll u = 1, ll s = 1, ll d = len) {
        prop(u, s, d);
        if(r < s || d < l) return {0, 0};
        if(l <= s && d <= r) 
            return {V[0][u], V[1][u]};
        auto [a, b] = query(l, r, u << 1, s, (s + d) >> 1);
        auto [x, y] = query(l, r, u << 1 | 1, ((s + d) >> 1) + 1, d);
        vector<ll> A = {a, b, x, y};
        sort(A.begin(), A.end());
        return {A[3], A[2]};
    }
};
map<ii, ll> Eid;
ii E[MN];
vector<ii> PozAfectate[MN]; // pt fiecare muchie, seg afectate in aint
vector<ii> trees; // seg pe aint ce reprezinta un centroid
vector<ll> ArbAfectati[MN]; // pt fiecare muchie, in ce seg de centr se afla

multiset<ii> bestByTree; // {sum, tree_id}
map<int, ll> ValoareArb;

void add_tree(ll u) {
    auto [st, dr] = trees[u];
    auto [a, b] = AINT::query(st, dr);
    //printf("La o modificare a arborelui %d(cu lim %d si %d) am gasit 2 maxime: %d si %d\n", u, st, dr, a, b);
    ValoareArb[u] = a + b;
    bestByTree.insert({a + b, u});
}

int W[MN];

void init() {
    cin >> n >> q >> max_weight;
    for(int i = 1; i < n; ++i) {
        ll u, v, w;
        cin >> u >> v >> w;
        E[i] = {u, v};
        W[i] = w;
        Eid[E[i]] = i; Eid[{v, u}] = i;
        L[u].push_back({v, w});
        L[v].push_back({u, w});
    }
    vector<int> Cpar(n + 1, 0), Sz(n + 1, 0);
    vector<bool> Used(n + 1, false);
    function<void(int, int)> dfi = [&] (int u, int p) {
        Sz[u] = 1;
        for(auto [it, w] : L[u])
            if(!Used[it] && it != p) dfi(it, u), Sz[u] += Sz[it];
    };
    function<int(int, int, int)> find_centroid = [&] (int u, int p, int bsz) {
        for(auto [it, w] : L[u])
            if(it != p && !Used[it] && Sz[it] * 2 > bsz) return find_centroid(it, u, bsz);
        return u;
    };
    int global_tmr = 0;
    function<void(int, int)> init_aint = [&] (int u, int p) {
        int st = global_tmr + 1;
        if(int(L[u].size()) == 1) { /// a leaf
            ++global_tmr;
        }   
        for(auto [it, w] : L[u])
            if(!Used[it] && it != p) init_aint(it, u);
        int dr = global_tmr;
        PozAfectate[Eid[{u, p}]].push_back({st, dr});
    };
    function<void(int, int, int)> dfs_afect = [&](int u, int p, int dest) {
        if(p) ArbAfectati[Eid[{u, p}]].push_back(dest);
        for(auto [it, w] : L[u])
            if(!Used[it] && it != p)
                dfs_afect(it, u, dest);
    };
    function<void(int, int)> desc = [&] (int u, int cpar) {
        int st = global_tmr + 1;
        dfi(u, 0);
        int c = find_centroid(u, 0, Sz[u]);
        Used[c] = 1;
        Cpar[c] = cpar;
        init_aint(c, 0);
        int dr = global_tmr;

        trees.push_back({st, 0});
        trees[int(trees.size()) - 1].second = dr;
        //printf("L-am scos pe %d ca centroid de la %d la %d\n", c, st, dr);
        dfs_afect(c, 0, int(trees.size()) - 1);
        for(auto [it, w] : L[c])
            if(!Used[it]) desc(it, c);
    };
    //printf("--------------------------\n");
    desc(1, 0);
    //printf("--------------------------\n");
    AINT::init(global_tmr + 1);
    for(int i = 1; i < n; ++i) {
        auto [u, v] = E[i];
        int w = W[i];
        //printf("Muchia %d afecteaza segmentele: ", i);
        for(auto [st, dr] : PozAfectate[i]) {
            AINT::add(st, dr, w);
            //printf(" & (%d, %d)", st, dr);
        } 
        //printf("\n");
    }
    //printf("--------------------------\n");
    for(int i = 0; i < trees.size(); ++i) add_tree(i);
}
void update(int muchie, ll w) {
    ll lw = W[muchie], delta = w - lw;
    //printf("Muchia %d %d isi schimba valoarea %d -> %d\n", E[muchie].first, E[muchie].second, lw, w);
    for(auto [st, dr] : PozAfectate[muchie]) {
        AINT::add(st, dr, delta);
    }
    W[muchie] = w;
    for(auto it : ArbAfectati[muchie])
        bestByTree.erase({ValoareArb[it], it});
    for(auto it : ArbAfectati[muchie])
        add_tree(it);
}
int main() {
    init();
    ll last = 0;
    for(int i = 1; i <= q; ++i) {
        int d; ll e;
        cin >> d >> e;
        d = (d + last) % (n - 1) + 1;
        e = (e + last) % max_weight;
        update(d, e);
        auto [v, id] = *bestByTree.rbegin();
        cout << v << "\n";
        last = v;
    }
    return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'void init()':
diameter.cpp:140:14: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  140 |         auto [u, v] = E[i];
      |              ^~~~~~
diameter.cpp:150:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     for(int i = 0; i < trees.size(); ++i) add_tree(i);
      |                    ~~^~~~~~~~~~~~~~

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