Submission #884753

#	Time	Username	Problem	Language	Result	Execution time	Memory
884753		radinr85	Dynamic Diameter (CEOI19_diameter)	C++14	31 / 100	272 ms	22004 KiB

diameter

//Radin (you can say Radan)
#include <bits/stdc++.h>

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

typedef long long ll;
typedef deque<int> dq;
typedef long double ld;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;

const int Mx = 101;
const int LOG = 23;
const ll INF = 2e18;
const int maxn = 3e6;
const ll mod = 1e9+7;

#define F first
#define S second
#define endl "\n"
#define lc id << 1
#define pb push_back
#define rc id << 1 | 1
#define all(x) (x).begin(),(x).end()
#define ms(x , y) memset(x , y , sizeof x)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll pw(ll a, ll b, ll md = mod){ll res=1;b=max(b,0ll);while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res%md);}

const int N = 1e5 + 10;
vector<pii> adj[N];
multiset<ll> seti;
ll lazy[N << 2];
ll seg[N << 2];
int col[N];
int st[N];
int fn[N];
int ch[N];
ll w[N];
ll h[N];
int n,q;
ll mx;

void shift(int id) {
	lazy[lc] += lazy[id];
	lazy[rc] += lazy[id];
	seg[lc] += lazy[id];
	seg[rc] += lazy[id];

	lazy[id] = 0;
}
void upd(int ql , int qr , ll val , int l = 0 , int r = n , int id = 1) {
	if(r <= ql || qr <= l)
		return;
	if(ql <= l && r <= qr) {
		lazy[id] += val;
		seg[id] += val;
		return;
	}
	shift(id);

	int mid = r + l >> 1;
	upd(ql , qr , val , l , mid , lc);
	upd(ql , qr , val , mid , r , rc);

	seg[id] = max(seg[lc] , seg[rc]);
}
ll get(int ql , int qr , int l = 0 , int r = n , int id = 1) {
	if(r <= ql || qr <= l)
		return 0;
	if(ql <= l && r <= qr)
		return seg[id];
	shift(id);

	int mid = r + l >> 1;
	return max(get(ql , qr , l , mid , lc) , get(ql , qr , mid , r , rc));
}
int t;
void dfs(int u , int p = 0) {
	col[u] = (p == 1 ? u : col[p]);
	st[u] = t ++;

	for(auto [v , id] : adj[u]) {
		if(v == p)
			continue;
		
		h[v] = h[u] + w[id];
		ch[id] = v;

		dfs(v , u);
	}
	fn[u] = t;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> n >> q >> mx;
	for(int i = 0 ; i < n-1 ; i ++) {
		ll u , v , W;
		cin >> u >> v >> W;

		adj[u].pb({v , i});
		adj[v].pb({u , i});
		w[i] = W;
	}
	dfs(1);

	for(int i = 1 ; i <= n ; i ++)
		upd(st[i] , st[i]+1 , h[i]);

	for(int i = 1 ; i <= n ; i ++) {
		if(col[i] != i)
			continue;
		
		seti.insert(-get(st[i] , fn[i]));
	}

	ll last = 0;
	while(q --) {
		ll d , e;
		cin >> d >> e;
		d = (d + last) % (n-1);
		e = (e + last) % mx;
		
		int u = ch[d];
		int v = col[u];

		seti.erase(seti.find(-get(st[v] , fn[v])));

		upd(st[u] , fn[u] , e - w[d]);

		seti.insert(-get(st[v] , fn[v]));

		w[d] = e;

		int cnt = 0;
		ll ans = 0;
		for(auto h : seti) {
			if(cnt == 2)
				break;
			ans += -1 * h;
			cnt ++;
		}
		cout << ans << endl;
		last = ans;
	}

	return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'void upd(int, int, ll, int, int, int)':
diameter.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |  int mid = r + l >> 1;
      |            ~~^~~
diameter.cpp: In function 'll get(int, int, int, int, int)':
diameter.cpp:77:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |  int mid = r + l >> 1;
      |            ~~^~~
diameter.cpp: In function 'void dfs(int, int)':
diameter.cpp:85:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |  for(auto [v , id] : adj[u]) {
      |           ^

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