Submission #934482

#	Time	Username	Problem	Language	Result	Execution time	Memory
934482		Romicro	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	298 ms	57656 KiB

diameter

#include <iostream>
#include <vector>

#define endl '\n'
#define pb push_back
#define ll long long

using namespace std;

const int MAXN = 1e5+100;
const ll INF = 1e18+109;

struct Edge{
	ll u, c;
};

struct FEdge{
	ll a, b, c;
};

struct node{
	ll mx, mn, a_2b, c_2b, rs;
};

node seg[1 << 20];
ll lz[1 << 20];

ll n, q;
ll sn = 1;
ll dx, ex;
ll lst;
ll w;

vector<Edge> adj[MAXN];
vector<ll> et;
ll d[MAXN];
ll st[MAXN], ft[MAXN];
bool used[MAXN];

vector<FEdge> edges;

void dfs(int v){
	used[v] = 1;
	st[v] = et.size();
	ft[v] = et.size();
	et.pb(d[v]);

	for(Edge e : adj[v]){
		if(used[e.u]) continue;
		d[e.u] = (d[v] + e.c);

		dfs(e.u);

		ft[v] = et.size();
		et.pb(d[v]);
	}
}

ll max(ll a, ll b){
	return (a > b)? a : b;
}

ll min(ll a, ll b){
	return (a < b)? a : b;
}

node combine(node a, node b){
	node res;
	
	res.mx = max(a.mx, b.mx);
	res.mn = min(a.mn, b.mn);
	res.a_2b = max(a.a_2b, b.a_2b);
	if(b.mn < INF and a.mx > -INF) res.a_2b = max(res.a_2b, a.mx - 2*b.mn);
	res.c_2b = max(a.c_2b, b.c_2b);
	if(a.mn < INF and b.mx > -INF) res.c_2b = max(res.c_2b, b.mx - 2*a.mn);
	res.rs = max(a.rs, b.rs);
	if(a.mx > -INF and b.mx > -INF and a.a_2b > -INF and b.c_2b > -INF) res.rs = max(res.rs, max(a.a_2b + b.mx, a.mx + b.c_2b));

	return res;
}

void shift(int v){
	if(v >= sn) return;
	int lc = (v<<1), rc=lc|1;

	ll x = lz[v];

	seg[lc].mx += x;
	seg[lc].mn += x;
	seg[lc].a_2b -= x;
	seg[lc].c_2b -= x;

	seg[rc].mx += x;
	seg[rc].mn += x;
	seg[rc].a_2b -= x;
	seg[rc].c_2b -= x;

	lz[lc] += x;
	lz[rc] += x;
	lz[v] = 0;
}
	

void add(int v, int vl, int vr, int l, int r, ll x){
	shift(v);
	if(vl > r or vr < l) return;

	if(l <= vl and vr <= r){
		seg[v].mx += x;
		seg[v].mn += x;
		seg[v].a_2b -= x;
		seg[v].c_2b -= x;

		lz[v] += x;
		return;
	}

	int vm = (vl + vr) >> 1;

	add((v<<1), vl, vm, l, r, x);
	add((v<<1)|1, vm+1, vr, l, r, x);

	seg[v] = combine(seg[(v<<1)], seg[(v<<1)|1]);
}


int main(){
	ios::sync_with_stdio(0);cin.tie(0);

	cin >> n >> q >> w;

	for(int i=0; i<n-1; i++){
		ll a, b, c;

		cin >> a >> b >> c;
		a--;b--;

		adj[a].pb({b, c});
		adj[b].pb({a, c});

		edges.pb({a, b, c});
	}

	dfs(0);

	while(sn < et.size()) sn <<= 1;

	for(int i=0; i<et.size(); i++){
		seg[i + sn].mn = et[i];
		seg[i + sn].mx = et[i];
		seg[i + sn].a_2b = -et[i];
		seg[i + sn].c_2b = -et[i];
		seg[i + sn].rs = 0;
	}

	node emp = {-INF, INF, -INF, -INF, -INF};

	for(int i=et.size(); i<sn; i++)
		seg[i + sn] = emp;

	for(int i=(sn-1); i>=1; i--)
		seg[i] = combine(seg[(i<<1)], seg[(i<<1)|1]);


	while(q--){
		cin >> dx >> ex;

		
		dx = (dx + (lst%(n-1)) ) % (n-1);
		ex = (ex + (lst%w) ) % w;

		FEdge e = edges[dx];
		if(d[e.a] > d[e.b]) swap(e.a, e.b);
		edges[dx].c = ex;

		add(1, 1, sn, st[e.b]+1, ft[e.b]+1, ex - e.c);


		cout << seg[1].rs << endl;
		lst = seg[1].rs;
	}
	

	return 0;
}	

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:146:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |  while(sn < et.size()) sn <<= 1;
      |        ~~~^~~~~~~~~~~
diameter.cpp:148:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |  for(int i=0; i<et.size(); i++){
      |               ~^~~~~~~~~~

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