Submission #579070

#	Time	Username	Problem	Language	Result	Execution time	Memory
579070		talant117408	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	5101 ms	242380 KiB

diameter

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define long                unsigned long 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'

const int N = 1e5+7;
set <pair <int, ll>> graph[N];
vector <pair <pii, ll>> edges;
vector <vector <ll>> tree(N), lz(N);
set <pair <int, pii>> eulers[N];
multiset <ll, greater <ll>> to_leaves[N], ans;
int subtree[N], level[N], parent[N][20], timer, par[N];
int n, q;
ll w;

void push(int i, int v, int l, int r) {
    if (lz[i][v] != 0) {
        tree[i][v] += lz[i][v];
        if (l != r) {
            lz[i][v*2] += lz[i][v];
            lz[i][v*2+1] += lz[i][v];
        }
        lz[i][v] = 0;
    }
}

void update(int i, int v, int l, int r, int ql, int qr, ll val) {
    push(i, v, l, r);
    if (ql > r || l > qr) return;
    if (ql <= l && r <= qr) {
        lz[i][v] += val;
        push(i, v, l, r);
        return;
    }
    int mid = (l+r) >> 1;
    update(i, v*2, l, mid, ql, qr, val);
    update(i, v*2+1, mid+1, r, ql, qr, val);
    tree[i][v] = max(tree[i][v*2], tree[i][v*2+1]);
}

ll get(int i, int v, int l, int r, int ql, int qr) {
    push(i, v, l, r);
    if (ql > r || l > qr) return -1e18;
    if (ql <= l && r <= qr) return tree[i][v];
    int mid = (l+r) >> 1;
    return max(get(i, v*2, l, mid, ql, qr), get(i, v*2+1, mid+1, r, ql, qr));
}

void find_subtrees(int v, int p) {
    subtree[v] = 1;
    for (auto to : graph[v]) {
        if (to.first == p || level[to.first]) continue;
        find_subtrees(to.first, v);
        subtree[v] += subtree[to.first];
    }
}

int find_centroid(int v, int p, int saizu) {
    for (auto to : graph[v]) {
        if (to.first == p || level[to.first]) continue;
        if (subtree[to.first]*2 > saizu) return find_centroid(to.first, v, saizu);
    }
    return v;
}

void cnd_dfs(int v, int p, ll dist, int &origin, int &saizu, int &lev, int &origin2) {
    pii range;
    range.first = ++timer;
    update(origin, 1, 0, saizu-1, timer, timer, dist);
    parent[v][lev] = origin2;
    
    for (auto to : graph[v]) {
        if (to.first == p || level[to.first]) continue;
        cnd_dfs(to.first, v, dist+to.second, origin, saizu, lev, origin2);
    }
    range.second = timer;
    eulers[origin].insert(mp(v, range));
}

void centroid_decomposition(int v, int p = 0, int lev = 1) {
    find_subtrees(v, v);
    auto centroid = find_centroid(v, v, subtree[v]);
    level[centroid] = lev;
    par[centroid] = p;
    
    tree[centroid].resize(subtree[v]*4);
    lz[centroid].resize(subtree[v]*4);
    timer = 0;
    for (auto to : graph[centroid]) {
        if (level[to.first]) continue;
        int prev = timer+1;
        cnd_dfs(to.first, centroid, to.second, centroid, subtree[v], lev, to.first);
        to_leaves[centroid].insert(get(centroid, 1, 0, subtree[v]-1, prev, timer));
    }
    eulers[centroid].insert(mp(centroid, mp(0, timer)));
    ll res = 0, cnt = 0;
    for (auto to : to_leaves[centroid]) {
        res += to;
        if (++cnt > 1) break;
    }
    ans.insert(res);
    
    for (auto to : graph[centroid]) {
        if (level[to.first]) continue;
        centroid_decomposition(to.first, centroid, lev+1);
    }
}

void solve() {
    cin >> n >> q >> w;
    for (int i = 0; i < n-1; i++) {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        if (a > b) swap(a, b);
        edges.pb(mp(mp(a, b), c));
        graph[a].insert(mp(b, c));
        graph[b].insert(mp(a, c));
    }
    centroid_decomposition(1);
    ll last = 0;
    while (q--) {
        ll d, e;
        cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % w; 
        auto a = edges[d].first.first, b = edges[d].first.second;
        auto &c = edges[d].second;
        if (level[a] > level[b]) swap(a, b);
        auto x = a;
        while (x) {
            {
                auto ita = (*eulers[x].lb(mp(a, mp(0, 0)))).second.first;
                auto itb = (*eulers[x].lb(mp(b, mp(0, 0)))).second.first;
                if (get(x, 1, 0, sz(eulers[x])-1, ita, ita) > get(x, 1, 0, sz(eulers[x])-1, itb, itb)) swap(a, b);
            }
            auto it = eulers[x].lb(mp(b, mp(0, 0)));
            auto range = (*it).second;
            auto pit = eulers[x].lb(mp(parent[b][level[x]], mp(0, 0)));
            auto prange = (*pit).second;
            ll res = 0, cnt = 0;
            for (auto to : to_leaves[x]) {
                res += to;
                if (++cnt > 1) break;
            }
            ans.erase(ans.find(res));
            to_leaves[x].erase(to_leaves[x].find(get(x, 1, 0, sz(eulers[x])-1, prange.first, prange.second)));
            update(x, 1, 0, sz(eulers[x])-1, range.first, range.second, e-c);
            to_leaves[x].insert(get(x, 1, 0, sz(eulers[x])-1, prange.first, prange.second));
            res = cnt = 0;
            for (auto to : to_leaves[x]) {
                res += to;
                if (++cnt > 1) break;
            }
            ans.insert(res);
            x = par[x];
        }
        cout << *ans.begin() << endl;
        c = e;
        last = *ans.begin();
    }
}

int main() {
    do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}
/*

*/

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