Submission #595540

#	Time	Username	Problem	Language	Result	Execution time	Memory
595540		rainliofficial	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	357 ms	86476 KiB

diameter

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define sz(x) (int)x.size()
#define f first
#define s second

/* 
Date: 2022/07/12 19:14
Problem Link: https://dmoj.ca/problem/ceoi19p2/
Topic(s): Segment tree, Euler tour
Time Spent:
Solution Notes:
By creating a segment tree, each node holds 4 values:
1. d_i = distance to the root
2. max(d_l - 2*d_m)
3. max(d_r - 2*d_m)
4. max(d_l + d_r - 2*d_m)
*/


const int MAXN = 1e5+5;
const ll INF = 5e17;
int n, q, in[MAXN], out[MAXN], dep[MAXN], timer = 0;
ll dp[MAXN];
vector<pair<int, ll>> arr[MAXN];
vector<int> tour;
ll w;

void dfs(int at, int p, int d, ll dist){
    tour.push_back(at);
    in[at] = timer++;
    dep[at] = d;
    dp[at] = dist;
    for (auto edge : arr[at]){
        if (edge.f != p){
            dfs(edge.f, at, d+1, dist + edge.s);
            tour.push_back(at);
            timer++;
        }
    }
    tour.push_back(at);
    out[at] = timer++;
}

struct Node{
    ll di_max, di_min, pre, suf, ans;
};

struct segtree{
    int n;
    Node identity = {0, INF, -INF, -INF, 0};
    vector<Node> seg;
    vector<ll> lazy;
    vector<ll> arr;
    segtree(int n){
        this->n = n;
        seg.resize(4*n, identity);
        lazy.resize(4*n);
    }
    void build(vector<ll>& arr){
        this->arr = arr;
        build(0, 0, n-1);
    }
    void build(int node, int l, int r){
        if (l == r) {
			seg[node] = {arr[l], arr[l], -arr[l], -arr[l], 0};
			return;
		}
		int mid = (l + r) / 2;
		build(node * 2 + 1, l, mid);
		build(node * 2 + 2, mid + 1, r);
		// change this
		seg[node] = combine(seg[node * 2 + 1], seg[node * 2 + 2]);
    }
    ll query(){
        return seg[0].ans;
    }
    void update(int a, int b, ll x) { // inclusive 0-indexed
		update(0, 0, n-1, a, b, x);
	}
    void update(int node, int l, int r, int a, int b, ll x) {
		int numElements = r - l + 1;
		if (a <= l && r <= b) { 
			apply(node, l, r, x);
			return;
		}
		prop(node, l, r);
		int mid = (l + r) / 2;
		if (a <= mid) {
			update(node * 2 + 1, l, mid, a, b, x);
		}
		if (b > mid) {
			update(node * 2 + 2, mid + 1, r, a, b, x);
		}
		// change this
		seg[node] = combine(seg[node * 2 + 1], seg[node * 2 + 2]);

	}
    void prop(int node, int l, int r) { // propagate the "lazy value"
		if (lazy[node] != 0) {
			int mid = (l + r) / 2;
			// change this
			apply(node*2+1, l, mid, lazy[node]);
			apply(node*2+2, mid+1, r, lazy[node]);
			lazy[node] = 0;
		}
	}
	void apply(ll node, ll l, ll r, ll x){
        seg[node].di_min += x;
        seg[node].di_max += x;
        seg[node].pre -= x;
        seg[node].suf -= x;
        lazy[node] += x;
    }
	Node combine(Node a, Node b){
        ll di_min = min(a.di_min, b.di_min);
        ll di_max = max(a.di_max, b.di_max);
        ll pre = max({a.pre, b.pre, a.di_max - 2*b.di_min});
        ll suf = max({a.suf, b.suf, b.di_max - 2*a.di_min});
        ll ans = max({a.ans, b.ans, a.pre + b.di_max, b.suf + a.di_max});
        return {di_max, di_min, pre, suf, ans};
    }
};


int main(){
    cin.tie(0); ios_base::sync_with_stdio(0);
    // freopen("file.in", "r", stdin);
    // freopen("file.out", "w", stdout);
    cin >> n >> q >> w;
    vector<array<ll, 3>> edges(n-1);
    for (int i=0; i<n-1; i++){
        int a, b;
        ll c;
        cin >> a >> b >> c;
        a--; b--;
        edges[i] = {a, b, c};
        arr[a].push_back({b, c});
        arr[b].push_back({a, c});
    }
    dfs(0, -1, 0, 0);
    vector<ll> segtreeInit;
    for (int i=0; i<sz(tour); i++){
        segtreeInit.push_back(dp[tour[i]]);
    }
    segtree st(sz(tour));
    st.build(segtreeInit);
    ll last = 0;
    for (int i=0; i<q; i++){
        int a;
        ll b;
        cin >> a >> b;
        a = (a + last)%(n-1);
        b = (b + last)%w;
        int subtree = dep[edges[a][0]] > dep[edges[a][1]] ? edges[a][0] : edges[a][1];
        st.update(in[subtree], out[subtree], b - edges[a][2]);
        edges[a][2] = b;
        last = st.query();
        cout << last << "\n";
    }
}

Compilation message (stderr)

diameter.cpp: In member function 'void segtree::update(int, int, int, int, int, ll)':
diameter.cpp:85:7: warning: unused variable 'numElements' [-Wunused-variable]
   85 |   int numElements = r - l + 1;
      |       ^~~~~~~~~~~

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