Submission #1119493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119493		mmdrzada	Dynamic Diameter (CEOI19_diameter)	C++17	24 / 100	315 ms	67516 KiB

diameter

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


typedef vector<int> vi;
typedef vector<char> vc;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
 
#define sep ' '
#define F first
#define S second
#define fastIO   ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define kill(x) {cout << x << endl;return;}
#define sz(x) int(x.size())
#define SP(x) setprecision(x) 
#define mod(x) (1ll*x%M+M)%M
#define pq priority_queue
#define mid (l+r)/2
// #define mid2 (l+r+1)/2
#define pll pair<ll, ll>
#define REP(i, k) for (int i = 0 ; i < k ; i ++)
#define MP make_pair
struct Node {
	ll a, b, c, d, e, lazy;
	Node () {
		a = b = c = d = e = -2e18;
		lazy = 0;
	}
};
const int M = 998244353;
const int N = 1e5+10;
int n, q; ll W;
vector<pair<int, ll>> adj[N];
ll h[N];
vector<pii> E, SE;
int st[N], fn[N];
vector<int> order;
Node node[N<<2];
vector<ll> Ws;
ll weight[N];

Node merge(Node x, Node y) {
	Node res;
	res.a = max(x.a, y.a);
	res.b = max(x.b, y.b);
	res.c = max({x.c, x.a + y.b, y.c});
	res.d = max({x.d, x.b + y.a, y.d});
	res.e = max({x.e, x.c + y.a, x.a + y.d, y.e});
	return res;
}

void dolazy(int id) {
	ll C = node[id].lazy;
	node[id].lazy = 0;
	vi ids = {2*id, 2*id+1};
	for(auto i: ids) {
		node[i].lazy += C;
		node[i].a += C;
		node[i].b -= 2*C;
		node[i].c -= C;
		node[i].d -= C;
	}
}

int ID(int u, int v) {
	if (u > v) swap(u, v);
	return lower_bound(SE.begin(), SE.end(), MP(u, v)) - SE.begin();
}

void dfs(int v = 0, int p = -1) {
	for(auto [neigh, w]: adj[v]) {
		if (neigh == p) continue;
		h[neigh] = 0ll + h[v] + w;
		order.pb(h[v]);
		st[ID(v, neigh)] = order.size();
		dfs(neigh, v);
		fn[ID(v, neigh)] = order.size();
	}
	order.pb(h[v]);
}

void build(int l = 0, int r = n, int id = 1) {
	if (r-l == 1) {
		node[id].a = order[l];
		node[id].b = -2ll*order[l];
		node[id].c = node[id].d = -order[l];
		node[id].e = 0;
		return;
	}
	build(l, mid, 2*id), build(mid, r, 2*id+1);
	node[id] = merge(node[2*id], node[2*id+1]);
}

void upd(int L, int R, ll C, int l=0, int r=n, int id=1) {
	if (R <= l || r <= L)
		return;
	if (L <= l && r <= R) {
		node[id].lazy += C;
		node[id].a += C;
		node[id].b -= 2*C;
		node[id].c -= C;
		node[id].d -= C;
		return;
	}
	dolazy(id);
	upd(L, R, C, l, mid, 2*id), upd(L, R, C, mid, r, 2*id+1);
	node[id] = merge(node[2*id], node[2*id+1]);
}
int get(int ind, int l=0, int r=n, int id=1) {
	if (r-l == 1) return node[id].a;
	dolazy(id);
	if (ind < mid) return get(ind, l, mid, 2*id);
	return get(ind, mid, r, 2*id+1);
}
void fulldata(int l=0, int r=n, int id=1) {
	cout << id << sep << l << sep << r << sep << node[id].a << sep << node[id].b << sep << node[id].e << endl;
	if (r-l > 1) fulldata(l, mid, 2*id), fulldata(mid, r, 2*id+1);
}
void solve() {
	cin >> n >> q >> W;
	int m = n;
	for(int i = 0 ; i < n-1 ; i ++) {
		int u, v, w; cin >> u >> v >> w; u--, v--; if (u > v) swap(u, v);
		adj[u].pb({v, w}), adj[v].pb({u, w});
		Ws.pb(w);
		E.pb({u, v});
	}
	SE = E;
	sort(SE.begin(), SE.end());
	for(int i = 0 ; i < n-1 ; i ++) {
		auto [u, v] = E[i];
		weight[ID(u, v)] = Ws[i];
	}
	dfs();
	n = 2*n-1;
	build();
	ll last = 0;
	while(q--) {
		ll d, w; cin >> d >> w;
		d = (0ll + d + last) % (m-1);
		w = (0ll + w + last) % W;
		auto [u, v] = E[d];
		int id = ID(u, v);
		int s = st[id], f = fn[id];
		// [s, f)
		upd(s, f, 0ll + w - weight[id]);
		weight[id] = w;
		cout << node[1].e << endl;
		last = node[1].e;
	}
}

// check MAXN
int32_t main() {
	fastIO;
	
	solve();
	
	return 0;
}

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