Submission #895864

#	Time	Username	Problem	Language	Result	Execution time	Memory
895864		math_rabbit_1028	Dynamic Diameter (CEOI19_diameter)	C++14	31 / 100	194 ms	48412 KiB

diameter

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

int n, q;
ll w;
ll edges[101010][3];
vector<pil> adj[101010];
int ch[101010], sz[101010];
int table[101010][20];
vector<int> child[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;
}

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

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

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

void sparse() {
    for (int k = 1; k < 20; k++) {
        for (int i = 1; i <= n; i++) {
            table[i][k] = table[table[i][k-1]][k-1];
        }
    }
}

int get_par(int v, int h) {
    for (int k = 0; k < 20; k++) {
        if (h & (1<<k)) v = table[v][k];
    }
    return v;
}

struct maxseg {
    pil tree[808080];
    ll lazy[808080];

    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) {
        tree[v].val += lazy[v];
        lazy[2*v] += lazy[v];
        lazy[2*v+1] += lazy[v];
        lazy[v] = 0;
    }

    void init(int v, int st, int ed) {
        if (st == ed) {
            tree[v] = {ord[st], dis[ord[st]]};
            lazy[v] = 0;
            return;
        }
        int mid = (st + ed) / 2;
        init(2*v, st, mid);
        init(2*v+1, mid+1, ed);
        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);
        if (lt <= st && ed <= rt) {
            lazy[v] = diff;
            prop(v);
            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);
        if (lt <= st && ed <= rt) return tree[v];
        if (st > rt || lt > ed) return {-1, -1};
        int mid = (st + ed) / 2;
        return mer(get(2*v, st, mid, lt, rt), get(2*v+1, mid+1, ed, lt, rt));
    }
} seg;

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});
    }

    //cent(1, n);

    table[1][0] = 1;
    ett(1);
    sparse();
    for (int i = 1; i < n; i++) {
        if (depth[edges[i][0]] > depth[edges[i][1]]) swap(edges[i][0], edges[i][1]);
    }

    seg.init(1, 1, n);

    ll last = 0;
    while (q--) {
        int d; ll e;
        cin >> d >> e;
        d = (d + last) % (n - 1) + 1;
        e = (e + last) % w;
        int v = edges[d][1];
        seg.upd(1, 1, n, in[v], out[v], e - edges[d][2]);
        edges[d][2] = e;

        pil x = seg.get(1, 1, n, 1, n);
        int u = get_par(x.idx, depth[x.idx] - 1);
        pil y = seg.get(1, 1, n, 1, in[u]-1);
        pil z = seg.get(1, 1, n, out[u]+1, n);
        last = x.val + max(y.val, z.val);
        cout << last << "\n";
    }

    return 0;
}

Compilation message (stderr)

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

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