Submission #542789

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
542789	2022-03-28T04:31:07 Z	blue	Dynamic Diameter (CEOI19_diameter)	C++17	42 / 100	4038 ms	298488 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'000LL;

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	20 ms	37460 KB	Output is correct
2	Correct	18 ms	37460 KB	Output is correct
3	Correct	19 ms	37540 KB	Output is correct
4	Correct	18 ms	37452 KB	Output is correct
5	Correct	18 ms	37536 KB	Output is correct
6	Correct	19 ms	37424 KB	Output is correct
7	Correct	20 ms	37540 KB	Output is correct
8	Correct	19 ms	37588 KB	Output is correct
9	Correct	18 ms	37460 KB	Output is correct
10	Correct	19 ms	37568 KB	Output is correct
11	Correct	20 ms	37692 KB	Output is correct
12	Correct	20 ms	37608 KB	Output is correct
13	Correct	20 ms	37560 KB	Output is correct
14	Correct	24 ms	37588 KB	Output is correct
15	Correct	19 ms	37628 KB	Output is correct
16	Correct	20 ms	37536 KB	Output is correct
17	Correct	20 ms	37628 KB	Output is correct
18	Correct	19 ms	37588 KB	Output is correct

Subtask #2

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	37460 KB	Output is correct
2	Correct	18 ms	37460 KB	Output is correct
3	Correct	19 ms	37540 KB	Output is correct
4	Correct	18 ms	37452 KB	Output is correct
5	Correct	18 ms	37536 KB	Output is correct
6	Correct	19 ms	37424 KB	Output is correct
7	Correct	20 ms	37540 KB	Output is correct
8	Correct	19 ms	37588 KB	Output is correct
9	Correct	18 ms	37460 KB	Output is correct
10	Correct	19 ms	37568 KB	Output is correct
11	Correct	20 ms	37692 KB	Output is correct
12	Correct	20 ms	37608 KB	Output is correct
13	Correct	20 ms	37560 KB	Output is correct
14	Correct	24 ms	37588 KB	Output is correct
15	Correct	19 ms	37628 KB	Output is correct
16	Correct	20 ms	37536 KB	Output is correct
17	Correct	20 ms	37628 KB	Output is correct
18	Correct	19 ms	37588 KB	Output is correct
19	Incorrect	38 ms	38796 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	37516 KB	Output is correct
2	Correct	20 ms	37460 KB	Output is correct
3	Correct	21 ms	37460 KB	Output is correct
4	Correct	34 ms	37708 KB	Output is correct
5	Correct	74 ms	38604 KB	Output is correct
6	Correct	21 ms	37508 KB	Output is correct
7	Correct	19 ms	37844 KB	Output is correct
8	Correct	20 ms	37916 KB	Output is correct
9	Correct	21 ms	37936 KB	Output is correct
10	Correct	40 ms	38148 KB	Output is correct
11	Correct	107 ms	39252 KB	Output is correct
12	Correct	27 ms	41524 KB	Output is correct
13	Correct	27 ms	41552 KB	Output is correct
14	Correct	30 ms	41620 KB	Output is correct
15	Correct	53 ms	41884 KB	Output is correct
16	Correct	149 ms	42980 KB	Output is correct
17	Correct	254 ms	118872 KB	Output is correct
18	Correct	240 ms	119076 KB	Output is correct
19	Correct	258 ms	118924 KB	Output is correct
20	Correct	298 ms	119304 KB	Output is correct
21	Correct	550 ms	120584 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	52 ms	39212 KB	Output is correct
3	Incorrect	207 ms	39904 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	2883 ms	232840 KB	Output is correct
2	Correct	3095 ms	237492 KB	Output is correct
3	Correct	3146 ms	236252 KB	Output is correct
4	Correct	3026 ms	237744 KB	Output is correct
5	Correct	2985 ms	228372 KB	Output is correct
6	Correct	2622 ms	188404 KB	Output is correct
7	Correct	3926 ms	277692 KB	Output is correct
8	Correct	3862 ms	277540 KB	Output is correct
9	Correct	3862 ms	277680 KB	Output is correct
10	Correct	3870 ms	276816 KB	Output is correct
11	Correct	3845 ms	266344 KB	Output is correct
12	Correct	3447 ms	210208 KB	Output is correct
13	Correct	3894 ms	298368 KB	Output is correct
14	Correct	3926 ms	298472 KB	Output is correct
15	Correct	3845 ms	298456 KB	Output is correct
16	Correct	3992 ms	297432 KB	Output is correct
17	Correct	3705 ms	284944 KB	Output is correct
18	Correct	3232 ms	217316 KB	Output is correct
19	Correct	3880 ms	298384 KB	Output is correct
20	Correct	3872 ms	298488 KB	Output is correct
21	Correct	3984 ms	298428 KB	Output is correct
22	Correct	4038 ms	297592 KB	Output is correct
23	Correct	3763 ms	284784 KB	Output is correct
24	Correct	3219 ms	217196 KB	Output is correct

Subtask #6

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	37460 KB	Output is correct
2	Correct	18 ms	37460 KB	Output is correct
3	Correct	19 ms	37540 KB	Output is correct
4	Correct	18 ms	37452 KB	Output is correct
5	Correct	18 ms	37536 KB	Output is correct
6	Correct	19 ms	37424 KB	Output is correct
7	Correct	20 ms	37540 KB	Output is correct
8	Correct	19 ms	37588 KB	Output is correct
9	Correct	18 ms	37460 KB	Output is correct
10	Correct	19 ms	37568 KB	Output is correct
11	Correct	20 ms	37692 KB	Output is correct
12	Correct	20 ms	37608 KB	Output is correct
13	Correct	20 ms	37560 KB	Output is correct
14	Correct	24 ms	37588 KB	Output is correct
15	Correct	19 ms	37628 KB	Output is correct
16	Correct	20 ms	37536 KB	Output is correct
17	Correct	20 ms	37628 KB	Output is correct
18	Correct	19 ms	37588 KB	Output is correct
19	Incorrect	38 ms	38796 KB	Output isn't correct
20	Halted	0 ms	0 KB	-