Submission #542790

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
542790	2022-03-28T04:34:17 Z	blue	Dynamic Diameter (CEOI19_diameter)	C++17	42 / 100	3918 ms	295856 KB

diameter

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
#define sz(x) int(x.size())

const int mx = 100'000;
const int lg = 17;
const ll INF = 2'000'000'000'000'000'00LL;

int n, q;
ll w;

vi a(1+mx), b(1+mx);
vll c(1+mx);
vi edge[1+mx];
vpll edgepair[1+mx];

multiset<ll> centmaxvals;
multiset<ll> subtreemaxvals[1+mx];





vi banned(1+mx, 0);


//nodes & edges indexed from 1, everything else from 0


vi depth(1+mx);
vi subtree(1+mx);

int cent;

void dfs0(int u, int p, vi& lst)
{
	lst.push_back(u);

	subtree[u] = 1;

	for(int v : edge[u])
	{
		if(v == p) continue;
		if(banned[v]) continue;

		depth[v] = 1 + depth[u];

		dfs0(v, u, lst);

		subtree[u] += subtree[v];
	}
}



vi grouplist[1+mx]; //done
vi centsubtree[1+mx]; //done
vi centnormdepth[1+mx]; //done
vll centnormdist[1+mx]; //done

vi centanc[1+mx]; //done

int centancind[1+mx][1+lg]; //done

int currind; //done

vi currnodeind(1+mx); //done

vi centprocessord; //done

vi centtreedepth(1+mx, 0); //done

vi reprlist[1+mx];


void dfs1(int u, int p)
{
	//this is preset to -1 for the root and p == u !!!


	for(pll vp : edgepair[u])
	{
		int v = vp.first;
		ll w = vp.second;

		if(v == p) continue;
		if(banned[v]) continue;

		// cerr << "used edge : " << u << " -> " << v << " at " << w << '\n';

		currind++;
		currnodeind[v] = currind;

		grouplist[cent][currind] = v;
		centsubtree[cent][currind] = 1;
		centnormdepth[cent][currind] = 1 + centnormdepth[cent][ currnodeind[u] ];
		centnormdist[cent][currind] = w + centnormdist[cent][ currnodeind[u] ];

		// cerr << "centnormdist " << cent << ' ' << currind << " = " << centnormdist[cent][currind] << '\n';
		dfs1(v, u);

		centsubtree[cent][ currnodeind[u] ] += centsubtree[cent][ currnodeind[v] ];
	}
}






struct segtree
{
	int S;
	int Z;

	vi l, r;
	vll mxv, lp;

	segtree()
	{
		;
	}

	void build(int i, int L, int R, vll& lst)
	{
		l[i] = L;
		r[i] = R;
		if(l[i] == r[i])
		{
			mxv[i] = lst[l[i]];
		}
		else
		{
			build(2*i, L, (L+R)/2, lst);
			build(2*i+1, (L+R)/2+1, R, lst);
			mxv[i] = max(mxv[2*i], mxv[2*i+1]);
		}
	}

	void add(int i, int L, int R, ll V)
	{
		if(R < l[i] || r[i] < L) return;
		else if(L <= l[i] && r[i] <= R)
		{
			mxv[i] += V;
			lp[i] += V;
		}
		else
		{
			add(2*i, L, R, V);
			add(2*i+1, L, R, V);
			mxv[i] = lp[i] + max(mxv[2*i], mxv[2*i+1]);
		}
	}

	ll rangemax(int i, int L, int R)
	{
		if(R < l[i] || r[i] < L) return -INF;
		else if(L <= l[i] && r[i] <= R) return mxv[i];
		else return lp[i] + max(rangemax(2*i, L, R), rangemax(2*i+1, L, R)); 
	}

	segtree(vll& lst)
	{
		S = sz(lst);
		Z = 4*S;

		l = r = vi(1+Z);
		mxv = lp = vll(1+Z, 0);

		build(1, 0, sz(lst)-1, lst);
	}
};


segtree CST[1+mx]; //done







bool firstbuild = 1;

int build(int u)
{
	// cerr << "building " << u << '\n';

	depth[u] = 0;

	cent = -1;

	vi lst;

	dfs0(u, u, lst);

	// cerr << "X\n";


	if(firstbuild) firstbuild = 0;
	else
	{
		for(int f : lst)
		{
			reprlist[f].push_back(u);
		}
	}
	



	for(int k : lst)
	{
		if(2*subtree[k] < sz(lst)) continue;
		if(cent == -1 || depth[k] > depth[cent])
			cent = k;
	}
	centprocessord.push_back(cent);


	// cerr << "F\n";

	grouplist[cent] = centsubtree[cent] = centnormdepth[cent] = vi(sz(lst));
	centnormdist[cent] = vll(sz(lst));


	currind = 0;
	currnodeind[cent] = 0;

	// cerr << "Z\n";

	grouplist[cent][0] = cent;

	centsubtree[cent][0] = 1;

	centnormdepth[cent][0] = 0;

	centnormdist[cent][0] = 0;

	// cerr << "Y\n";

	dfs1(cent, cent);


	// cerr << "\n\n\n";
	// cerr << "currently building centroid = " << cent << '\n';
	// cerr << "grouplist = ";
	// for(int z : grouplist[cent]) cerr << z << ' ';
	// 	cerr << '\n';
	// cerr << "distances = ";
	// for(ll z : centnormdist[cent]) cerr << z << ' ';
	// 	cerr << '\n';



	CST[cent] = segtree(centnormdist[cent]);

	int localcent = cent;

	banned[localcent] = 1;

	// cerr << "Z\n";

	for(int z : edge[localcent])
	{
		if(banned[z]) continue;


		// cerr << "build : " << cent << " -> " << z << '\n';
		int d = build(z);

		centanc[d].push_back(localcent);
	}

	banned[localcent] = 0;

	return localcent;
};


ll gettwosum(int u)
{
	auto it = subtreemaxvals[u].rbegin();
	auto it2 = it;
	it2++;
	return *it + *it2;
}

void disablemax(int u)
{
	centmaxvals.erase(gettwosum(u));
}

void enablemax(int u)
{
	centmaxvals.insert(gettwosum(u));
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> q;
	cin >> w;

	for(int e = 1; e <= n-1; e++)
	{
		cin >> a[e] >> b[e] >> c[e];


		edge[a[e]].push_back(b[e]);
		edge[b[e]].push_back(a[e]);

		edgepair[a[e]].push_back({b[e], c[e]});
		edgepair[b[e]].push_back({a[e], c[e]});
	}

	// cerr << "A\n";

	//init

	for(int i = 1; i <= n; i++)
	{
		centanc[i].push_back(i);
		centancind[i][0] = 0;
	}


	int rt = build(1);
	for(int i = 1; i <= n; i++)
	{
		// cerr << "\n\n\n seeing reprlist of " << i << "\n";
		reprlist[i].push_back(i);
		reverse(reprlist[i].begin(), reprlist[i].end());
		// for(int t : reprlist[i]) cerr << t << ' ';
		// 	cerr << '\n';
	}

	// cerr << "B\n";

	for(int i = 1; i <= n; i++)
		while(centanc[i].back() != rt)
			centanc[i].push_back( centanc[ centanc[i].back() ][1] );

	// cerr << "B1\n";

	for(int u : centprocessord)
	{
		centtreedepth[u] = sz(centanc[u]) - 1;
	}

	// cerr << "B2\n";

	for(int i = 1; i <= n; i++)
	{
		for(int z = 0; z < sz(grouplist[i]); z++)
		{
			int j = grouplist[i][z];

			centancind[j][ centtreedepth[j] - centtreedepth[i] ] = z;
		}
	}

	// for(int qv : grouplist[5]) cerr << qv << ' ';
	// 	cerr << '\n';

	// cerr << "cent tree depth = ";
	// for(int i = 1; i <= n; i++) cerr << centtreedepth[i] << ' ';
	// 	cerr << '\n';
	// cerr << "C\n";

	// cerr << "5 ind = ";
	// for(int i = 1; i <= n; i++) cerr << centancind[i][centtreedepth[i] - centtreedepth[5]] << ' ';
	// 	cerr << '\n';


	for(int i = 1; i <= n; i++)
	{
		// cerr << "\n\n\n";
		// cerr << "i = " << i << '\n';
		subtreemaxvals[i].insert(0);
		subtreemaxvals[i].insert(0);

		// for(int h = 0; h < sz(grouplist[i]); h++) cerr << CST[i].rangemax(1, h, h) << ' ';
		// 	cerr << '\n';


		for(int j : edge[i])
		{
			if(centtreedepth[j] <= centtreedepth[i]) continue;


			int jrep = reprlist[j][ centtreedepth[j] - centtreedepth[i] ];
			// cerr << "checking " << i << " -> " << j << " = " << jrep <<  '\n';

			int dd = centtreedepth[jrep] - centtreedepth[i];

			// cerr << "dd = " << dd << '\n';


			int jrepid = centancind[jrep][dd];
			int jrepst = centsubtree[i][ jrepid ];

			// for(int h = 0; h < sz(grouplist[i]); h++)
			// 	cerr << grouplist[i][h] << " - " << centsubtree[i][h] << '\n';

			// cerr << "j interval = ";
			// cerr << jrepid << ' ' << jrepst << '\n';

			// cerr << "#\n";


			subtreemaxvals[i].insert(CST[i].rangemax(1, jrepid, jrepid+jrepst-1));
		}
		// cerr << i << " done\n";
	}

	// cerr << "D\n";




	// cerr << "\n\n\n\n\n";
	// for(int i = 1; i <= n; i++)
	// {
	// 	cerr << '\n';
	// 	cerr << i << " : ";
	// 	for(int j : grouplist[i]) cerr << j << ' ';
	// 		cerr << '\n';

	// 	cerr << i << " : ";
	// 	for(ll y : subtreemaxvals[i]) cerr << y << ' ';
	// 		cerr << '\n';
	// }
	// cerr << "\n\n\n\n\n";



	// ce

	for(int i = 1; i <= n; i++) centmaxvals.insert(gettwosum(i));



	// cerr << "preliminary answer = " << *centmaxvals.rbegin() << '\n';





	ll last = 0;

	for(int j = 1; j <= q; j++)
	{
		// cerr << "\n\n";
		// cerr << "j = " << j << " started\n";
		ll d;
		ll e;
		cin >> d >> e;

		// cerr << e << " + " << last << '\n';

		d = ((d + last) % ll(n-1)) + 1;
		e = (e + last) % w;

		// cerr << "actual values = " << d << ' ' << e << '\n';

		ll delta = e - c[d];

		c[d] = e;

		//update

		int x = a[d], y = b[d];

		if(centtreedepth[x] > centtreedepth[y]) swap(x, y);

		int depx = centtreedepth[x], depy = centtreedepth[y];

		int depu = depx, depv = depy;
		int u = x, v = y;

		// cerr << "#\n";

		// cerr << "???\n";

		// cerr << u << ' ' << depu << " : " << v << ' ' << depv << '\n';

		for(int ndep = depx; ndep >= 0; ndep--)
		{
			// cerr << "\n\n";
			// cerr << "ndep = " << ndep <<'\n';
			if(centanc[u][depu - ndep] != centanc[v][depv - ndep]) continue;
			// cerr << "entered\n";

			if(centnormdepth[centanc[u][depu - ndep]][centancind[u][depu - ndep]] > centnormdepth[centanc[v][depv - ndep]][centancind[v][depv - ndep]])
			{
				swap(u, v);
				swap(depu, depv);
			}

			// cerr << "hello\n";

			int a = centanc[u][depu - ndep];

			// cerr << "a = " << a << '\n';

			// cerr << "segment tree = ";
			// for(int li = 0; li < sz(grouplist[a]); li++)
			// 	cerr << CST[a].rangemax(1, li, li) << ' ';
			// cerr << "\n";

			disablemax(a);

			// cerr << "max disabled at " << a << '\n';

			// cerr << "index of " << v << " at " << a << " = " << vid << '\n';

			int vid = centancind[v][depv - ndep];

			// cerr << "index of " << v << " at " << a << " = " << vid << '\n';
			int vst = centsubtree[a][vid];

			// cerr << "hello\n";

			// cerr << a << ' ' << sz(grouplist[a]) << ' ' << vid << ' ' << vst << '\n';

			// cerr << "trying to erase " << CST[a].rangemax(1, vid, vid+vst-1) << '\n';

			// for(ll rv : subtreemaxvals[a]) cerr << "rv = " << rv << '\n';

			// cerr << "inspecting\n";

			// cerr << "value erased\n";

			int vrep = reprlist[v][depv - ndep];
			int vrepid = centancind[vrep][ centtreedepth[vrep] - centtreedepth[a] ];
			int vrepst = centsubtree[ a ][ vrepid ];


			subtreemaxvals[a].erase(subtreemaxvals[a].find(CST[a].rangemax(1, vrepid, vrepid+vrepst-1)));

			// cerr << "reached flag\n";

			CST[a].add(1, vid, vid+vst-1, delta);

			subtreemaxvals[a].insert(CST[a].rangemax(1, vrepid, vrepid+vrepst-1));

			enablemax(a);
		}


		// cerr << "centroid = 2\n";
		// for(ll b : subtreemaxvals[2])
		// 	cerr << "b = " << b << '\n';






		// cerr << "\n\n\n\n DECLARING ANSWER\n";
		last = *centmaxvals.rbegin();
		cout << last << '\n';


	}
}

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	37460 KB	Output is correct
2	Correct	18 ms	37540 KB	Output is correct
3	Correct	18 ms	37580 KB	Output is correct
4	Correct	20 ms	37480 KB	Output is correct
5	Correct	18 ms	37520 KB	Output is correct
6	Correct	18 ms	37424 KB	Output is correct
7	Correct	18 ms	37460 KB	Output is correct
8	Correct	20 ms	37464 KB	Output is correct
9	Correct	18 ms	37532 KB	Output is correct
10	Correct	18 ms	37532 KB	Output is correct
11	Correct	17 ms	37588 KB	Output is correct
12	Correct	18 ms	37532 KB	Output is correct
13	Correct	19 ms	37588 KB	Output is correct
14	Correct	17 ms	37568 KB	Output is correct
15	Correct	18 ms	37588 KB	Output is correct
16	Correct	21 ms	37560 KB	Output is correct
17	Correct	19 ms	37652 KB	Output is correct
18	Correct	21 ms	37636 KB	Output is correct

Subtask #2

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	37460 KB	Output is correct
2	Correct	18 ms	37540 KB	Output is correct
3	Correct	18 ms	37580 KB	Output is correct
4	Correct	20 ms	37480 KB	Output is correct
5	Correct	18 ms	37520 KB	Output is correct
6	Correct	18 ms	37424 KB	Output is correct
7	Correct	18 ms	37460 KB	Output is correct
8	Correct	20 ms	37464 KB	Output is correct
9	Correct	18 ms	37532 KB	Output is correct
10	Correct	18 ms	37532 KB	Output is correct
11	Correct	17 ms	37588 KB	Output is correct
12	Correct	18 ms	37532 KB	Output is correct
13	Correct	19 ms	37588 KB	Output is correct
14	Correct	17 ms	37568 KB	Output is correct
15	Correct	18 ms	37588 KB	Output is correct
16	Correct	21 ms	37560 KB	Output is correct
17	Correct	19 ms	37652 KB	Output is correct
18	Correct	21 ms	37636 KB	Output is correct
19	Incorrect	41 ms	38880 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #3

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	37460 KB	Output is correct
2	Correct	22 ms	37460 KB	Output is correct
3	Correct	20 ms	37512 KB	Output is correct
4	Correct	31 ms	37740 KB	Output is correct
5	Correct	76 ms	38652 KB	Output is correct
6	Correct	19 ms	37444 KB	Output is correct
7	Correct	19 ms	37864 KB	Output is correct
8	Correct	20 ms	37844 KB	Output is correct
9	Correct	22 ms	37892 KB	Output is correct
10	Correct	38 ms	38192 KB	Output is correct
11	Correct	104 ms	39200 KB	Output is correct
12	Correct	30 ms	41548 KB	Output is correct
13	Correct	28 ms	41516 KB	Output is correct
14	Correct	29 ms	41556 KB	Output is correct
15	Correct	51 ms	41860 KB	Output is correct
16	Correct	149 ms	43040 KB	Output is correct
17	Correct	246 ms	119024 KB	Output is correct
18	Correct	234 ms	118892 KB	Output is correct
19	Correct	251 ms	119080 KB	Output is correct
20	Correct	322 ms	119220 KB	Output is correct
21	Correct	596 ms	120688 KB	Output is correct

Subtask #4

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	39084 KB	Output is correct
2	Correct	48 ms	39232 KB	Output is correct
3	Incorrect	218 ms	39784 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #5

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2871 ms	231700 KB	Output is correct
2	Correct	2946 ms	236256 KB	Output is correct
3	Correct	2866 ms	234796 KB	Output is correct
4	Correct	2869 ms	236116 KB	Output is correct
5	Correct	2821 ms	226844 KB	Output is correct
6	Correct	2557 ms	186820 KB	Output is correct
7	Correct	3773 ms	275568 KB	Output is correct
8	Correct	3794 ms	275556 KB	Output is correct
9	Correct	3748 ms	275476 KB	Output is correct
10	Correct	3799 ms	274432 KB	Output is correct
11	Correct	3640 ms	264164 KB	Output is correct
12	Correct	3462 ms	207948 KB	Output is correct
13	Correct	3758 ms	295804 KB	Output is correct
14	Correct	3672 ms	295664 KB	Output is correct
15	Correct	3724 ms	295856 KB	Output is correct
16	Correct	3623 ms	294380 KB	Output is correct
17	Correct	3588 ms	281764 KB	Output is correct
18	Correct	3115 ms	214116 KB	Output is correct
19	Correct	3841 ms	295376 KB	Output is correct
20	Correct	3704 ms	295484 KB	Output is correct
21	Correct	3833 ms	295180 KB	Output is correct
22	Correct	3918 ms	294248 KB	Output is correct
23	Correct	3557 ms	281196 KB	Output is correct
24	Correct	3124 ms	213740 KB	Output is correct

Subtask #6

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	37460 KB	Output is correct
2	Correct	18 ms	37540 KB	Output is correct
3	Correct	18 ms	37580 KB	Output is correct
4	Correct	20 ms	37480 KB	Output is correct
5	Correct	18 ms	37520 KB	Output is correct
6	Correct	18 ms	37424 KB	Output is correct
7	Correct	18 ms	37460 KB	Output is correct
8	Correct	20 ms	37464 KB	Output is correct
9	Correct	18 ms	37532 KB	Output is correct
10	Correct	18 ms	37532 KB	Output is correct
11	Correct	17 ms	37588 KB	Output is correct
12	Correct	18 ms	37532 KB	Output is correct
13	Correct	19 ms	37588 KB	Output is correct
14	Correct	17 ms	37568 KB	Output is correct
15	Correct	18 ms	37588 KB	Output is correct
16	Correct	21 ms	37560 KB	Output is correct
17	Correct	19 ms	37652 KB	Output is correct
18	Correct	21 ms	37636 KB	Output is correct
19	Incorrect	41 ms	38880 KB	Output isn't correct
20	Halted	0 ms	0 KB	-