Submission #1150051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150051		CodeLakVN	Dynamic Diameter (CEOI19_diameter)	C++20	0 / 100	58 ms	42248 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, ll> il;
typedef pair<int, int> ii;

const int N = 1e5 + 5;

struct IT {
    vector<ll> tree, lazy;
    int n;

    void init(int _n) {
        n = _n;
        tree.assign(4 * n + 3, 0);
        lazy.assign(4 * n + 3, 0);
    }

    void down(int id) {
        if (lazy[id] == 0) return;
        ll s = lazy[id];
        tree[2 * id] += s;
        lazy[2 * id] += s;
        tree[2 * id + 1] += s;
        lazy[2 * id + 1] += s;
        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]);
    }

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

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

    ll get(int u, int v) {
        return get(1, 1, n, u, v);
    }
} maxTree[N];

struct EDGE {
    int v, id;
    ll w;
};

int numNode, numQuery;
ll limit;
vector<EDGE> adj[N];
ll w[N];
ii edges[N];

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

int countChild(int u, int p) {
    sz[u] = 1;
    for (EDGE e : adj[u]) {
        int v = e.v;
        if (v == p || del[v]) continue;
        sz[u] += countChild(v, u);
    }
    return sz[u];
}

int centroid(int u, int p, int m) {
    for (EDGE e : adj[u]) {
        int v = e.v;
        if (v == p || del[v]) continue;
        if (sz[v] > m / 2) return centroid(v, u, m);
    }
    return u;
}

int root;
int id[N];
vector<int> in[N], out[N], com[N], sonOfRoot[N];
vector<ll> dist[N];

void addNode(int u, int p) {
    com[root].push_back(u);
    for (EDGE e : adj[u]) {
        int v = e.v;
        if (v == p || del[v]) continue;
        addNode(v, u);
    }
}

int timer = 0;
vector<int> par[N];

void prepare(int u, int p, ll dist) {
    if (u != root) in[root][id[u]] = ++timer, maxTree[root].update(timer, timer, dist);
    for (EDGE e : adj[u]) {
        int v = e.v;
        ll c = e.w;
        if (v == p || del[v]) continue;
        par[e.id].push_back(root);
        sonOfRoot[root][id[v]] = (u == root ? id[v] : sonOfRoot[root][id[u]]);
        prepare(v, u, dist + c);
    }
    if (u != root) out[root][id[u]] = timer;
}

multiset<ll, greater<ll>> branchesValues[N];
multiset<ll, greater<ll>> allValues;
int high[N];

ll diameter(multiset<ll, greater<ll>> s) {
    if (s.empty()) return 0;
    if (s.size() == 1) return *s.begin();
    else {
        auto it = s.begin();
        ll x = *it;
        it++;
        ll y = *it;
        return x + y;
    }
}

void decompose(int u) {
    root = u = centroid(u, -1, countChild(u, -1));
    del[u] = 1;

    for (EDGE e : adj[u]) {
        int v = e.v;
        if (del[v]) continue;
        addNode(v, u);
    }

    int m = com[u].size();
    if (m == 0) return;

    sort(com[u].begin(), com[u].end());
    FOR(i, 0, m - 1) id[com[u][i]] = i;

    in[u].resize(sz[u] + 1);
    out[u].resize(sz[u] + 1);
    sonOfRoot[u].resize(sz[u] + 1);
    maxTree[u].init(m);
    timer = 0;
    prepare(u, -1, 0);

    for (EDGE e : adj[u]) {
        int v = e.v;
        if (del[v]) continue;
        branchesValues[u].insert(maxTree[u].get(in[u][id[v]], out[u][id[v]]));
    }
    allValues.insert(diameter(branchesValues[u]));

    for (EDGE e : adj[u]) {
        int v = e.v;
        if (del[v]) continue;
        decompose(v);
    }

    return;
}

int ID(int root, int node) {
    return lower_bound(com[root].begin(), com[root].end(), node) - com[root].begin();
}

void update(int id, int u, int v, ll val) {
    for (int root : par[id]) {
        int ID_U = ID(root, u), ID_V = ID(root, v);
        if (root == u);
        else if (root == v) swap(ID_U, ID_V);
        else if (in[root][ID_U] > in[root][ID_V]) swap(ID_U, ID_V);

        int x = sonOfRoot[root][ID_V];
        allValues.erase(allValues.find(diameter(branchesValues[root])));
        branchesValues[root].erase(branchesValues[root].find(maxTree[root].get(in[root][x], out[root][x])));

        maxTree[root].update(in[root][ID_V], out[root][ID_V], val);
        branchesValues[root].insert(maxTree[root].get(in[root][x], out[root][x]));
        allValues.insert(diameter(branchesValues[root]));
    }
}

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;
        cin >> u >> v >> w[i];
        edges[i] = {u, v};
        adj[u].push_back({v, i, w[i]});
        adj[v].push_back({u, i, w[i]});
    }

    decompose(1);

    ll last = 0;
    FOR(i, 1, numQuery) {
        ll edgesID;
        ll newW;
        cin >> edgesID >> newW;
        edgesID = (edgesID + last) % (numNode - 1) + 1;
        newW = (newW + last) % limit;
        
        int u, v;
        tie(u, v) = edges[edgesID];
        if (high[u] > high[v]) swap(u, v);
        update(edgesID, u, v, -w[edgesID] + newW);
        w[edgesID] = newW;
        last = *allValues.begin();
        cout << last << "\n";
    }

    return 0;
}

Compilation message (stderr)

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

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