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
#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';


	}
}
# 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
# 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 -
# 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
# 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 -
# 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
# 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 -