Submission #856525

#	Time	Username	Problem	Language	Result	Execution time	Memory
856525		hocky	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	347 ms	64528 KiB

diameter

#include "bits/stdc++.h"

using namespace std;
const int LIM = 100000;
#define fi first
#define se second
typedef long long LL;
typedef pair<LL,LL> PLL;

namespace DynamicDiameter {
    vector <PLL> edge[LIM + 5];
    int event[2 * LIM + 5];
    int dfsTime = 0;
    LL weights[LIM + 5], depth[LIM + 5];
    PLL order[LIM + 5];
    void eulerTour(int pos, int par = -1) {
        dfsTime++;
        order[pos].fi = dfsTime;
        event[dfsTime] = pos;
        for (auto &nx: edge[pos]) {
            if (nx.fi == par) continue;
            depth[nx.fi] = depth[pos] + nx.se;
            weights[nx.fi] = nx.se;
            eulerTour(nx.fi, pos);
            dfsTime++;
            event[dfsTime] = pos;
        }
        order[pos].se = dfsTime;
        return;
    }
    
    const LL INF = 1e14;
    // Segment Tree starts here
    struct Node{
		LL maxDepth = -INF, minDepth = INF;
		LL leftMax = -INF, rightMax = -INF;
		LL diameter = 0;
		LL lazy;
	};
	
	Node segt[8 * LIM + 5];
	void pushDown(int rangeL = 1, int rangeR = dfsTime, int idx = 1){
		if(segt[idx].lazy == 0) return;
		auto &val = segt[idx].lazy;
		segt[idx].maxDepth += val;
		segt[idx].minDepth += val;
		segt[idx].leftMax -= val;
		segt[idx].rightMax -= val;
		if(rangeL != rangeR){
			segt[idx * 2].lazy += val;
			segt[idx * 2 + 1].lazy += val;
		}
		val = 0;
		return;
	}
	void merge(Node &head, Node &l, Node &r){
		head.maxDepth = max(l.maxDepth, r.maxDepth);
		head.minDepth = min(l.minDepth, r.minDepth);
		
		head.leftMax = max(l.leftMax, r.leftMax);
		head.leftMax = max(head.leftMax, l.maxDepth - 2 * r.minDepth);
		
		head.rightMax = max(l.rightMax, r.rightMax);
		head.rightMax = max(head.rightMax, r.maxDepth - 2 * l.minDepth);
		
		head.diameter = max(l.diameter, r.diameter);
		head.diameter = max(head.diameter, l.maxDepth + r.rightMax);
		head.diameter = max(head.diameter, r.maxDepth + l.leftMax);
		//~ cout << head.maxDepth << " " << head.minDepth << " " << head.leftMax << " " << head.rightMax << " " << head.diameter << endl;
	}
	void build(int rangeL = 1, int rangeR = dfsTime, int idx = 1){
		//~ cout << rangeL << " " << rangeR << " " << idx << endl;
		if(rangeL == rangeR){
			segt[idx].minDepth = segt[idx].maxDepth = depth[event[rangeL]];
			segt[idx].leftMax = segt[idx].rightMax = -depth[event[rangeL]];
			return;
		}
		int mid = (rangeL + rangeR) >> 1;
		build(rangeL, mid, idx * 2);
		build(mid + 1, rangeR, idx * 2 + 1);
		merge(segt[idx], segt[idx * 2], segt[idx * 2 + 1]);
	}
    void update(int queryL, int queryR, LL val, int rangeL = 1, int rangeR = dfsTime, int idx = 1){
		pushDown(rangeL, rangeR, idx);
		if(rangeR < queryL) return;
		if(queryR < rangeL) return; 
		if(queryL <= rangeL && rangeR <= queryR){
			segt[idx].lazy = val;
			pushDown(rangeL, rangeR, idx);
			return;
		}
		int mid = (rangeL + rangeR) >> 1;
		update(queryL, queryR, val, rangeL, mid, idx * 2);
		update(queryL, queryR, val, mid + 1, rangeR, idx * 2 + 1);
		merge(segt[idx], segt[idx * 2], segt[idx * 2 + 1]);
		return;
	}
}

using namespace DynamicDiameter;

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);
	LL n, q, w; cin >> n >> q >> w;
	vector <PLL> edges(n - 1);
    for (int i = 0; i < n - 1; i++) {
		LL c;
        cin >> edges[i].fi >> edges[i].se >> c;
        edge[edges[i].fi].emplace_back(edges[i].se, c);
        edge[edges[i].se].emplace_back(edges[i].fi, c);
    }
    eulerTour(1);
    //~ for(int i = 1;i <= dfsTime;i++) cout << event[i] << " ";
    //~ cout << endl;
    //~ for(int i = 1;i <= n;i++) cout << i << " " << order[i].fi << " " << order[i].se << endl;
    build();
    LL ans = 0;
    //~ cout << segt[1].diameter << endl;
    //~ return 0;
    while(q--){
		LL d, e; cin >> d >> e;
		d = (d + ans) % (n - 1);
		e = (e + ans) % w;
		auto &edge = edges[d];
		if(order[edge.fi].fi > order[edge.se].fi) {
			swap(edge.fi, edge.se);
		}
		// Update the segment tree
		//~ cout << e - weights[edge.se] << endl;
		//~ cout << segt[1].diameter << endl;
		update(order[edge.se].fi, order[edge.se].se, e - weights[edge.se]);
		weights[edge.se] = e;
		pushDown();
		ans = segt[1].diameter;
		cout << ans << endl;
	}
}

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