Submission #1151354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151354		CodeLakVN	Dynamic Diameter (CEOI19_diameter)	C++20	42 / 100	5097 ms	203628 KiB

diameter

#include <bits/stdc++.h>
using namespace std;

#define task "DIAMETER"
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define F first
#define S second
#define ll long long

typedef pair<int, int> ii;
typedef pair<int, ll> il;

const int N = (int)1e5 + 5;

int numNode, numQuery;
ll limit;

struct EDGE {
    int u, v;
    ll w;
};
vector<il> adj[N];
EDGE edges[N];

int sz[N];
bool del[N];

vector<ii> ancestors[N]; // storing ancestors of current node: {anc, DFS time of current node}

multiset<ll> candidates;

struct TREE {
    vector<ll> tree, lazy, dist, branchValue;
    vector<int> up; // storing the son which is an ancestor of current node and directly connected with the root
    vector<ii> sons; // storing sons of current node with its DFS time
    vector<int> out, directSon;
    int n, root;

    void init() {
        tree.assign(4 * n + 3, 0);
        lazy.assign(4 * n + 3, 0);
        branchValue.resize(n + 2);
        dist.assign(n + 2, 0);
        out.resize(n + 2);
        up.resize(n + 2);
    }

    // SEGMENT TREE LAZY UPDATE + MAX QUERY
    void build(int id, int l, int r) {
        if (l == r) {
            tree[id] = dist[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(2 * id, l, mid);
        build(2 * id + 1, mid + 1, r);
        tree[id] = max(tree[2 * id], tree[2 * id + 1]);
    }

    void down(int id) {
        if (lazy[id] == 0) return;
        tree[2 * id] += lazy[id];
        tree[2 * id + 1] += lazy[id];
        lazy[2 * id] += lazy[id];
        lazy[2 * id + 1] += lazy[id];
        lazy[id] = 0;
    }

    void update(int id, int l, int r, int u, int v, ll val) {
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            tree[id] += val;
            lazy[id] += val;
            return;
        }
        down(id);
        int mid = (l + r) >> 1;
        update(2 * id, l, mid, u, v, val);
        update(2 * id + 1, mid + 1, r, u, v, val);
        tree[id] = max(tree[2 * id], tree[2 * id + 1]);
    }

    void update(int u, int v, ll val) {
        update(1, 1, n, u, v, val);
    }

    ll get(int id, int l, int r, int u, int v) {
        if (l > v || r < u) return 0;
        if (l >= u && r <= v) return tree[id];
        down(id);
        int mid = (l + r) >> 1;
        return max(get(2 * id, l, mid, u, v), get(2 * id + 1, mid + 1, r, u, v));
    }

    ll get(int l, int r) {
        return get(1, 1, n, l, r);
    }

    // BUILD TREE
    int timer = 0;
    multiset<ll> values;

    void dfs(int u, int p) {
        int in = ++timer;
        ancestors[u].push_back({root, timer});
        sons.push_back({u, timer});
        for (auto [v, w] : adj[u]) if (v != p && !del[v]) {
            dist[timer + 1] = dist[in] + w;
            up[timer + 1] = (p == -1 ? timer + 1 : up[timer]);
            if (p == -1) directSon.push_back(timer + 1);
            dfs(v, u);
        }
        out[in] = timer;
    }

    int ID(int node) {
        return lower_bound(sons.begin(), sons.end(), make_pair(node, 0)) - sons.begin();
    }

    ll best(multiset<ll> s) {
        if (s.size() == 1) return *s.begin();
        auto it = prev(s.end());
        return *it + *(prev(it));
    }

    void construct(int u, int _n) {
        root = u, n = _n;
        init();
        dfs(u, -1);
        build(1, 1, n);
        sort(sons.begin(), sons.end());
        for (int ID_V : directSon) {
            branchValue[ID_V] = get(ID_V, out[ID_V]);
            values.insert(branchValue[ID_V]);
        }
        candidates.insert(best(values));
    }

    void change(int ID_U, ll val, int v) {
        int ID_V = ID(v);
        if (ID_V == n || sons[ID_V].F != v) return;
        ID_V = sons[ID_V].S;
        if (ID_V < ID_U) swap(ID_U, ID_V);

        candidates.erase(candidates.find(best(values)));
        int in = up[ID_V];
        values.erase(values.find(branchValue[in]));

        update(ID_V, out[ID_V], val);
        branchValue[in] = get(in, out[in]);
        values.insert(branchValue[in]);
        candidates.insert(best(values));
    } 
} tree[N];

int countChild(int u, int p) {
    sz[u] = 1;
    for (auto [v, w] : adj[u]) if (v != p && !del[v]) {
        sz[u] += countChild(v, u);
    }
    return sz[u];
}

int centroid(int u, int p, int m) {
    for (auto [v, w] : adj[u]) if (v != p && !del[v]) {
        if (sz[v] > m / 2) return centroid(v, u, m);
    }
    return u;
}

void decompose(int u, int p) {
    int x = centroid(u, -1, countChild(u, -1));
    del[x] = 1;
    if (sz[u] > 1) tree[x].construct(x, sz[u]);

    for (auto [v, w] : adj[x]) if (!del[v]) {
        decompose(v, x);
    }
}

int main() {
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> numNode >> numQuery >> limit;
    FOR(i, 1, numNode - 1) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        edges[i] = {u, v, w};
    }

    decompose(1, -1);
    // return 0;

    ll last = 0;
    while (numQuery--) {
        ll edgeID, newW;
        cin >> edgeID >> newW;
        edgeID = (edgeID + last) % (numNode - 1) + 1;
        newW = (newW + last) % limit;
        for (ii r : ancestors[edges[edgeID].u]) {
            int root = r.F, ID_U = r.S;
            tree[root].change(ID_U, -edges[edgeID].w + newW, edges[edgeID].v);
        } 
        edges[edgeID].w = newW;
        cout << (last = *(candidates.rbegin())) << "\n";
    }

    return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:184:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:185:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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