Submission #895914

#	Time	Username	Problem	Language	Result	Execution time	Memory
895914		math_rabbit_1028	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	3985 ms	540072 KiB

diameter

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef struct {
    int idx;
    ll val;
} pil;

int n, q;
ll w;
ll edges[101010][3];
vector<pil> adj[101010];
int ch[101010], sz[101010];

struct subtree {
    int cent, tot, r, d;
    vector<pil> ord;
    unordered_map<int, int> in, out, depth, dir, child;

    void ett(int v, ll dis, int par = -1) {
        ord[++r] = {v, dis}; in[v] = r;
        if (par != -1) dir[v] = d;
        for (int i = 0; i < adj[v].size(); i++) {
            int u = adj[v][i].idx;
            if (u == par) continue;
            if (ch[u] == 1) continue;
            depth[u] = depth[v] + 1;
            if (par == -1) d = u;
            ett(u, dis + adj[v][i].val, v);
        }
        out[v] = r;
    }

    struct maxseg {
        vector<pil> tree;
        vector<ll> lazy;

        pil mer(pil lt, pil rt) {
            if (lt.val > rt.val) return lt;
            if (lt.val < rt.val) return rt;
            if (lt.val == rt.val) {
                if (lt.idx > rt.idx) return lt;
                else return rt;
            }
        }

        void prop(int v, int st, int ed) {
            tree[v].val += lazy[v];
            if (st != ed) {
                lazy[2*v] += lazy[v];
                lazy[2*v+1] += lazy[v];
            }
            lazy[v] = 0;
        }

        void init(int v, int st, int ed, vector<pil>* ord) {
            if (st == ed) {
                tree[v] = (*ord)[st];
                lazy[v] = 0;
                return;
            }
            int mid = (st + ed) / 2;
            init(2*v, st, mid, ord);
            init(2*v+1, mid+1, ed, ord);
            tree[v] = mer(tree[2*v], tree[2*v+1]);
        }

        void upd(int v, int st, int ed, int lt, int rt, ll diff) {
            prop(v, st, ed);
            if (lt <= st && ed <= rt) {
                lazy[v] = diff;
                prop(v, st, ed);
                return;
            }
            if (st > rt || lt > ed) return;
            int mid = (st + ed) / 2;
            upd(2*v, st, mid, lt, rt, diff);
            upd(2*v+1, mid+1, ed, lt, rt, diff);
            tree[v] = mer(tree[2*v], tree[2*v+1]);
        }

        pil get(int v, int st, int ed, int lt, int rt) {
            prop(v, st, ed);
            if (lt <= st && ed <= rt) return tree[v];
            if (st > rt || lt > ed) return {0, 0};
            int mid = (st + ed) / 2;
            return mer(get(2*v, st, mid, lt, rt), get(2*v+1, mid+1, ed, lt, rt));
        }
    } seg;

    void init() {
        r = 0;
        for (int i = 0; i <= tot; i++) ord.push_back({0, 0});
        seg.tree.resize(4*tot);
        seg.lazy.resize(4*tot);

        ett(cent, 0);

        seg.init(1, 1, tot, &ord);
    }

    int update(int d, ll e) {
        int v = (depth[edges[d][0]] > depth[edges[d][1]] ? edges[d][0] : edges[d][1]);
        int u = (depth[edges[d][0]] < depth[edges[d][1]] ? edges[d][0] : edges[d][1]);
        seg.upd(1, 1, tot, in[v], out[v], e - edges[d][2]);
        return (u != cent ? child[dir[v]] : 0);
    }

    int get(ll* dst) {
        pil x = seg.get(1, 1, tot, 1, tot);
        int u = dir[x.idx];
        pil y = seg.get(1, 1, tot, 1, in[u]-1);
        pil z = seg.get(1, 1, tot, out[u]+1, tot);
        *dst = max(*dst, x.val + max(y.val, z.val));
        return child[u];
    }

} sub[101010];

void get_sz(int v, int par = -1) {
    sz[v] = 1;
    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i].idx;
        if (ch[u] == 1) continue;
        if (u == par) continue;
        get_sz(u, v);
        sz[v] += sz[u];
    }
}

int get_cent(int tot, int v, int par = -1) {
    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i].idx;
        if (ch[u] == 1) continue;
        if (u == par) continue;
        if (sz[u] * 2 > tot) return get_cent(tot, u, v);
    }
    return v;
}

int cent(int v, int tot) {
    get_sz(v);
    v = get_cent(tot, v);
    get_sz(v);

    sub[v].tot = tot;
    sub[v].cent = v;
    sub[v].init();

    ch[v] = 1;
    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i].idx;
        if (ch[u] == 1) continue;
        sub[v].child[u] = cent(u, sz[u]);
    }

    return v;
}

void update(int cent, int d, ll e) {
    while (sub[cent].tot > 1) {
        cent = sub[cent].update(d, e);
    }
}

void get(int cent, ll* dst) {
    while (sub[cent].tot > 1) {
        cent = sub[cent].get(dst);
    }
}

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

    cin >> n >> q >> w;

    for (int i = 1; i < n; i++) {
        int a, b; ll c;
        cin >> a >> b >> c;
        edges[i][0] = a;
        edges[i][1] = b;
        edges[i][2] = c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }

    int CENT = cent(1, n);

    ll last = 0;
    while (q--) {
        int d; ll e;
        cin >> d >> e;

        d = (d + last) % (n - 1) + 1;
        e = (e + last) % w;

        update(CENT, d, e);
        edges[d][2] = e;

        last = -1;
        get(CENT, &last);
        cout << last << "\n";
    }

    return 0;
}

Compilation message (stderr)

diameter.cpp: In member function 'void subtree::ett(int, ll, int)':
diameter.cpp:23:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pil>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for (int i = 0; i < adj[v].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~
diameter.cpp: In function 'void get_sz(int, int)':
diameter.cpp:122:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pil>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     for (int i = 0; i < adj[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
diameter.cpp: In function 'int get_cent(int, int, int)':
diameter.cpp:132:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pil>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for (int i = 0; i < adj[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
diameter.cpp: In function 'int cent(int, int)':
diameter.cpp:151:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pil>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |     for (int i = 0; i < adj[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
diameter.cpp: In member function 'pil subtree::maxseg::mer(pil, pil)':
diameter.cpp:45:9: warning: control reaches end of non-void function [-Wreturn-type]
   45 |         }
      |         ^

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