Submission #1004742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004742		vjudge1	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	2990 ms	103152 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;

struct AINT {
    int n;
    vector<ll> Ma, Lz;

    AINT() {}
    AINT(int N) : n(N), Ma(4 * N, 0), Lz(4 * N, 0) {}

    void prop(int u, int s, int d) {
        if(!Lz[u]) return;
        Ma[u] += Lz[u];
        if(s != d) {
            Lz[u << 1] += Lz[u];
            Lz[u << 1 | 1] += Lz[u];
        }
        Lz[u] = 0;
    }

    void update(int l, int r, ll v, int u, int s, int d) {
        prop(u, s, d);
        if(d < l || r < s) return;
        if(l <= s && d <= r) {
            Lz[u] += v;
            prop(u, s, d);
            return;
        }
        update(l, r, v, u << 1, s, (s + d) >> 1);
        update(l, r, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
        Ma[u] = max(Ma[u << 1], Ma[u << 1 | 1]);
    }
    void update(int l, int r, ll v) {
        update(l, r, v, 1, 0, n - 1);
    }

    ll query(int l, int r, int u, int s, int d) {
        prop(u, s, d);
        if(l <= s && d <= r) return Ma[u];
        if( d < l || r < s) return -1;
        return max(query(l, r, u << 1, s, (s + d) >> 1),
            query(l, r, u << 1 | 1, ((s + d) >> 1) + 1, d));
    }

    ll query(int st, int dr) {
        return query(st, dr, 1, 0, n - 1);
    }
};

namespace tree {
    int n;
    int tmr = 0;
    vi niv, euler, on, sz;
    vector<ll> cost;
    vector<vector<ii> > L;

    multiset<ll> Profi;
    struct InfoCent {
        multiset<ll> V;
        ll profit = 0;
        void change(ll a, ll b) {
            Profi.erase(Profi.find(profit));
            V.erase(V.find(a));
            V.insert(b);

            ll vm = *V.rbegin();
            profit = vm;
            V.erase(V.find(vm));
            if(!V.empty()) 
                profit += *V.rbegin();
            V.insert(vm);

            Profi.insert(profit);
        }
    };

    vector<InfoCent> Info;

    struct comp {
        int st, dr, cent;
        ll val;
    };
    vector<comp> Componente;

    vector< vector<ii> > SegMuchie;
    vector<vi> CompMuchie;

    AINT Sol;

    void init(int N) {
        n = N;
        niv.assign(N, 0);
        on.assign(N, 1);
        sz.assign(N, 0);
        cost.assign(N, 0);
        L.resize(N);
        Info.resize(N);
        SegMuchie.resize(N);
        CompMuchie.resize(N);
    }

    void add_edge(int u, int v, int id) {
        L[u].push_back({v, id});
        L[v].push_back({u, id});
    }



    void init() {
        function<void(int, int)> dfs_sz = [&](int u, int p) {
            sz[u] = 1;
            for(auto [it, id] : L[u])
                if(it != p && on[it]) {
                    dfs_sz(it, u);
                    sz[u] += sz[it];
                }
        };

        function<int(int, int, int)> find_c = [&](int u, int p, int sz_lim) {
            for(auto [it, id] : L[u])
                if(on[it] && it != p && 2 * sz[it] > sz_lim) return find_c(it, u, sz_lim);
            return u;
        };

        function<void(int, int, int, int)> dfs_comp = [&](int u, int p, int id_par, int cur_comp) {
            int in = tmr;
            int nr_fii = 0;
            for(auto [it, id] : L[u]) {
                if(it == p || !on[it]) continue;
                ++nr_fii;
                dfs_comp(it, u, id, cur_comp);
            }
            if(!nr_fii) { /// sunt o frunza, ++tmr!
                ++tmr;
            }
            int out = tmr - 1;
            ///id_par afecteaza {in, out}
            SegMuchie[id_par].push_back({in, out});
            CompMuchie[id_par].push_back(cur_comp);
        };

        function<void(int, int)> desc_cent = [&](int u, int parc) {
            Profi.insert(0);
            dfs_sz(u, -1);
            int c = find_c(u, -1, sz[u]);
            on[c] = 0;
            for(auto [it, id] : L[c]) {
                if(on[it]) {
                    ///componenta noua
                    int eu = Componente.size();
                    int in = tmr;
                    dfs_comp(it, c, id, eu);
                    int out = tmr - 1;
                    Componente.push_back({in, out, c, 0});
                    Info[c].V.insert(0);
                }
            }
            for(auto [it, id] : L[c]) {
                if(on[it]) {
                    desc_cent(it, c);
                }
            }
        };

        desc_cent(0, -1);
        Sol = AINT(tmr); 
    }

    void update(int id, ll w) {
        w -= cost[id];
        cost[id] += w;
        for(auto [st, dr] : SegMuchie[id]) {
            Sol.update(st, dr, w);
        }
        for(auto comp : CompMuchie[id]) {
            auto &[st, dr, cent, val] = Componente[comp];
            ll v2 = Sol.query(st, dr);
            Info[cent].change(val, v2);
            val = v2;
        }
    }

    ll diam() {
        return *Profi.rbegin();
    }
};

struct edge {
    int u, v;
    ll w;
};

int main() {
    int n, q;
    ll w_max;
    cin >> n >> q >> w_max;
    tree::init(n);
    vector<edge> E;
    for(int i = 1; i < n; ++i) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        --u; --v;
        E.push_back({u, v, w});
        tree::add_edge(u, v, i - 1);
    }
    tree::init();
    for(int i = 0; i < E.size(); ++i)
        tree::update(i, E[i].w);
    ll last = 0;
    for(int i = 0; i < q; ++i) {
        ll d, e;
        cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % w_max;
        tree::update((int)d, e);
        cout << (last = tree::diam()) << "\n";
    }
    return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:213:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  213 |     for(int i = 0; i < E.size(); ++i)
      |                    ~~^~~~~~~~~~

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