Submission #249605

#	Time	Username	Problem	Language	Result	Execution time	Memory
249605		mieszko11b	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	4696 ms	130252 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second

using ll = long long;
using ii = pair<int, int>;
using pll = pair<ll, ll>;

struct SegmentTree {
	int lv;
	ll d[270007], ins[270007];
	
	SegmentTree(int n = 100000) {
		lv = 2;
		while(lv < n + 2)
			lv *= 2;
	}
	
	void insert(int a, int b, int l, int r, int w, ll x) {
		if(b < l || a > r || l > r)
			return ;
		if(a <= l && r <= b) {
			d[w] += x;
			ins[w] += x;
			return ;
		}
		insert(a, b, l, (l + r) / 2, 2 * w, x);
		insert(a, b, (l + r) / 2 + 1, r, 2 * w + 1, x);
		d[w] = max(d[2 * w], d[2 * w + 1]) + ins[w];
	}
	
	void insert(int a, int b, ll x) {
		insert(a, b, 0, lv - 1, 1, x);
	}
	
	ll query(int a, int b, int l, int r, int w) {
		if(b < l || a > r || l > r)
			return 0;
		if(a <= l && r <= b)
			return d[w];
		ll p1 = query(a, b, l, (l + r) / 2, 2 * w);
		ll p2 = query(a, b, (l + r) / 2 + 1, r, 2 * w + 1);
		return max(p1, p2) + ins[w];
	}
	
	ll query(int a, int b) {
		return query(a, b, 0, lv - 1, 1);
	}
	
	void initv(int i, ll x) {
		d[lv + i] = x;
	}
	
	void process_init() {
		for(int i = lv - 1 ; i >= 1 ; i--)
			d[i] = max(d[2 * i], d[2 * i + 1]);
	}
};

int n, q;
ll w;
vector<pll> G[100007];
bool del[100007];
int innum[20][100007], outnum[20][100007];
int nxtnum[20];
int h[100007];
int vis[100007], viscnt;
int centro, total;
int sz[100007];
vector<int> ch[100007];
set<pll, greater<pll> > S[100007];
set<pll, greater<pll> > global;
ll globald[100007];
int p[100007];
SegmentTree ST[20];
ii E[100007];
ll ecost[100007];
ll prevv[20][100007];

void dfs(int w) {
	sz[w] = 1;
	vis[w] = viscnt;
	for(auto p : G[w]) {
		if(!del[p.X] && vis[p.X] != viscnt) {
			dfs(p.X);
			sz[w] += sz[p.X];
		}
	}
}

void dfs2(int w) {
	int maxsz = 0;
	vis[w] = viscnt;
	for(auto p : G[w]) {
		if(!del[p.X] && vis[p.X] != viscnt) {
			dfs2(p.X);
			maxsz = max(maxsz, sz[p.X]);
		}
	}
	maxsz = max(maxsz, total - sz[w]);
	if(maxsz <= total / 2)
		centro = w;
}

void dfs3(int w, int lvl, ll dist = 0) {
	innum[lvl][w] = outnum[lvl][w] = nxtnum[lvl]++;
	vis[w] = viscnt;
	ST[lvl].initv(innum[lvl][w], dist);
	for(auto p : G[w]) {
		if(!del[p.X] && vis[p.X] != viscnt) {
			dfs3(p.X, lvl, dist + p.Y);
			outnum[lvl][w] = max(outnum[lvl][w], outnum[lvl][p.X]);
		}
	}
}

int build(int w, int lvl) {
	viscnt++;
	dfs(w);
	total = sz[w];
	viscnt++;
	dfs2(w);
	
	int c = centro;
	h[c] = lvl;
	
	viscnt++;
	dfs3(c, lvl);
	
	del[c] = 1;
	for(auto p : G[c]) {
		if(!del[p.X]) {
			ch[c].push_back(p.X);
			::p[build(p.X, lvl + 1)] = c;
		}
	}
	return c;
}

void upd_global(int w) {
	ll d = 0;
	if(S[w].size() >= 1)
		d += S[w].begin()->X;
	if(S[w].size() >= 2)
		d += next(S[w].begin())->X;
	global.erase({globald[w], w});
	globald[w] = d;
	global.insert({globald[w], w});
}

ll get_answer() {
	if(global.empty())
		return 0;
	return global.begin()->X;
}

void update(int e, ll x) {
	ll delta = x - ecost[e];
	ecost[e] = x;
	
	int c;
	if(h[E[e].X] < h[E[e].Y])
		c = E[e].X;
	else
		c = E[e].Y;
		
	//~ cout << "c= "<< c << endl;
		
	while(c) {
		int w;
		if(innum[h[c]][E[e].X] > innum[h[c]][E[e].Y])
			w = E[e].X;
		else
			w = E[e].Y;
		
		int pocz = 0, kon = ch[c].size() - 1, mid;
		while(pocz < kon) {
			mid = (pocz + kon) / 2;
			if(outnum[h[c]][ch[c][mid]] >= innum[h[c]][w])
				kon = mid;
			else
				pocz = mid + 1;
		}
		
		int u = ch[c][pocz];
		
		//~ cout << w << " "<< u << endl;
		
		ll prevv = ::prevv[h[c]][u];
		if(prevv == -1)
			prevv = ST[h[c]].query(innum[h[c]][u], outnum[h[c]][u]);
		S[c].erase({prevv, u});
		ST[h[c]].insert(innum[h[c]][w], outnum[h[c]][w], delta);
		ll newv = ST[h[c]].query(innum[h[c]][u], outnum[h[c]][u]);
		S[c].insert({newv, u});
		::prevv[h[c]][u] = newv;
		
		upd_global(c);
		
		c = p[c];
	}
	
	//~ cout << "global: ";
	//~ for(auto p : global)
		//~ cout << "(" << p.X << ", " << p.Y << ") ";
	//~ cout << endl;
	//~ cout << "S[10]: ";
	//~ for(auto p : S[10])
		//~ cout << "(" << p.X << ", " << p.Y << ") ";
	//~ cout << endl;
}

int main() {
	memset(prevv, -1, sizeof prevv);
	
	scanf("%d%d%lld", &n, &q, &w);
	for(int i = 1 ; i < n ; i++) {
		int a, b;
		ll c;
		scanf("%d%d%lld", &a, &b, &c);
		G[a].emplace_back(b, c);
		G[b].emplace_back(a, c);
		E[i] = {a, b};
		ecost[i] = c;
	}
	
	build(1, 0);

	//~ for(int i = 1 ; i <= n ; i++)
		//~ cout << i << " " << p[i] << endl;

	for(int i = 0 ; i < 20 ; i++)
		ST[i].process_init();
		
	for(int i = 1 ; i <= n ; i++) {
		for(int j : ch[i])
			S[i].insert({ST[h[i]].query(innum[h[i]][j], outnum[h[i]][j]), j});
		upd_global(i);
	}
			
	ll last = 0;
	while(q--) {
		ll d, e;
		scanf("%lld%lld", &d, &e);
		d = (d + last) % (n - 1);
		e = (e + last) % w;
		
		update(d + 1, e);
		last = get_answer();
		printf("%lld\n", last);
	}
	
	return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:219:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lld", &n, &q, &w);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:223:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:247:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   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