Submission #343649

#	Time	Username	Problem	Language	Result	Execution time	Memory
343649		parsabahrami	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	758 ms	49356 KiB

diameter

//! The Leader Of Retards Bemola
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;
 
#define sz(x)                       (ll) x.size()
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define lc 							id << 1
#define rc 							lc | 1

ll Pow(ll a, ll b, ll md, ll ans = 1) {
    for (; b; b >>= 1, a = a * a % md)
        if (b & 1)
            ans = ans * a % md;
    return ans % md;
}
const ll MAXN = 2e5 + 10;
const ll INF  = 8e18;
const ll MOD  = 1e9 + 7;
struct Node {
	ll a, b, ab, bc, abc;
};

Node operator+(const Node &x, const Node &y) {
	Node sg; sg.abc = max({x.a + y.bc, x.abc, y.abc, x.ab + y.a});
	sg.a = max(x.a, y.a);
	sg.b = min(x.b, y.b);
	sg.bc = max({x.bc, y.bc, y.a - 2 * x.b});
	sg.ab = max({x.ab, y.ab, x.a - 2 * y.b});
	return sg;
}

ll lazy[MAXN << 2], L[MAXN], R[MAXN], W[MAXN], last, n, q, timer, w;
vector<pll> adj[MAXN]; Node seg[MAXN << 2];

void DFS(ll v, ll p = -1) {
	for (pll u : adj[v]) {
		if (u.F == p) continue;
		L[u.S] = ++timer;
		DFS(u.F, v);
		R[u.S] = ++timer;
	}
}

void shift(ll id, ll l, ll r) {
	seg[id].a += lazy[id];
	seg[id].b += lazy[id];
	seg[id].ab -= lazy[id];
	seg[id].bc -= lazy[id];
	if (r - l > 1) {
		lazy[lc] += lazy[id];
		lazy[rc] += lazy[id];
	}
	lazy[id] = 0;
}

void update(ll ql, ll qr, ll x, ll id = 1, ll l = 0, ll r = timer) {
	shift(id, l, r);
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr) {
		lazy[id] += x;
		return shift(id, l, r);
	}
	ll mid = (l + r) >> 1;
	shift(lc, l, mid), shift(rc, mid, r);
	update(ql, qr, x, lc, l, mid);
	update(ql, qr, x, rc, mid, r);
	seg[id] = seg[lc] + seg[rc];
}

int main() {
	scanf("%lld%lld%lld", &n, &q, &w);
	for (ll i = 1; i < n; i++) {
		ll u, v; scanf("%lld%lld%lld", &u, &v, &W[i]);
		adj[u].push_back({v, i});
		adj[v].push_back({u, i});
	}
	DFS(1);
	for (ll i = 1; i < n; i++) {
		update(L[i], R[i], W[i]);
	}
	while (q--) {
		ll d, e; scanf("%lld%lld", &d, &e);
		d = (d + last) % (n - 1) + 1;
		e = (e + last) % w;
		update(L[d], R[d], e - W[d]);
		W[d] = e;
		printf("%lld\n", last = seg[1].abc);
	}
    return 0;
}
 

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |  scanf("%lld%lld%lld", &n, &q, &w);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:79:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |   ll u, v; scanf("%lld%lld%lld", &u, &v, &W[i]);
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:88:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |   ll d, e; scanf("%lld%lld", &d, &e);
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~

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