Submission #495297

#	Time	Username	Problem	Language	Result	Execution time	Memory
495297		sare	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	1115 ms	129312 KiB

diameter

//In the name of Allah :)
#include <bits/stdc++.h>
using namespace std;
string to_string(char c) { return string(1,c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
template<class A> string to_string(complex<A> c) { 
	stringstream ss; ss << c; return ss.str(); }
string to_string(vector<bool> v) { 
	string res = "{"; for(int i = 0; i < (int)v.size(); i++) res += char('0'+v[i]);
	res += "}"; return res; }
template<size_t SZ> string to_string(bitset<SZ> b) {
	string res = ""; for(size_t i = 0; i < SZ; i++) res += char('0'+b[i]);
	return res; }
template<class A, class B> string to_string(pair<A,B> p);
template<class T> string to_string(T v) { // containers with begin(), end()
	bool fst = 1; string res = "{";
	for (const auto& x: v) {
		if (!fst) res += ", ";
		fst = 0; res += to_string(x);
	}
	res += "}"; return res;
}
template<class A, class B> string to_string(pair<A,B> p) {
	return "("+to_string(p.first)+", "+to_string(p.second)+")"; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define wis(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__)
#else
#define wis(...) 0
#endif
typedef long long ll;
#define all(x) (x).begin(), (x).end()
const int MAXN = 2e5 + 10;
const ll INF = 4e18;

int n, q, down[MAXN], st[MAXN], ft[MAXN], T;
ll tw[MAXN], w[MAXN], W;
vector<pair<int, int>> adj[MAXN];

struct Node {
	ll dp[4][4], lazy;

	Node (ll x = 0) {
		fill(&dp[0][0], &dp[3][3], x);
		for (int i = 0; i < 4; i++) {
			dp[i][i] = 0;
		}
		lazy = 0;
	}
} seg[MAXN << 2];

inline Node merge (const Node& x, const Node& y) {
	Node res(-INF);
	for (int i = 0; i < 4; i++) {
		for (int j = i; j < 4; j++) {
			for (int k = i; k <= j; k++) {
				res.dp[i][j] = max(res.dp[i][j], x.dp[i][k] + y.dp[k][j]);
			}
		}
	}
	return res;
}

void dfs (int v, int p) {
	st[v] = T++;
	for (auto [u, i] : adj[v]) {
		if (u == p) {
			continue;
		}
		down[i] = u;
		w[u] = tw[i];
		dfs(u, v);
		T++;
	}
	ft[v] = T;
}

inline void update (int nd, ll x) {
	auto cof = [&](int l, int r) {
		int ret = 0;
		if (l < 1 && 1 <= r) {
			ret++;
		}
		if (l < 2 && 2 <= r) {
			ret -= 2;
		}
		if (l < 3 && 3 <= r) {
			ret++;
		}
		return ret;
	};

	for (int i = 0; i < 4; i++) {
		for (int j = i; j < 4; j++) {
			seg[nd].dp[i][j] += x * cof(i, j);
		}
	}
	seg[nd].lazy += x;
}

inline void shift (int nd) {
	int L = nd << 1, R = L | 1;
	update(L, seg[nd].lazy);
	update(R, seg[nd].lazy);
	seg[nd].lazy = 0;
}

void add (int nd, int cl, int cr, int l, int r, ll x) {
	if (cl == l && cr == r) {
		update(nd, x);
		return;
	}
	shift(nd);
	int L = nd << 1, R = L | 1, mid = (cl + cr) >> 1;
	if (l < mid) {
		add(L, cl, mid, l, min(r, mid), x);
	}
	if (r > mid) {
		add(R, mid, cr, max(mid, l), r, x);
	}
	seg[nd] = merge(seg[L], seg[R]);
}
inline void add (int l, int r, ll x) {
	add(1, 0, T, l, r, x);
}

int main() {
	ios::sync_with_stdio(0);
#ifndef LOCAL
	cin.tie(0);
#endif
	cin >> n >> q >> W;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v >> tw[i];
		u--, v--;
		adj[u].emplace_back(v, i);
		adj[v].emplace_back(u, i);
	}

	dfs(0, -1);
	for (int i = 0; i < n - 1; i++) {
		int v = down[i];
		add(st[v], ft[v], w[v]);
	}

	ll last = 0;
	while (q--) {
		int e;
		ll x;
		cin >> e >> x;
		e = (e + last) % (n - 1);
		x = (x + last) % W;

		int v = down[e];
		add(st[v], ft[v], x - w[v]);
		w[v] = x;

		last = seg[1].dp[0][3];
		cout << last << '\n';
	}
}

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