oj.uz

Submission #542937

# Submission time Handle Problem Language Result Execution time Memory
542937 2022-03-28T13:26:38 Z blue Dynamic Diameter (CEOI19_diameter) C++17
42 / 100
 4500 ms 391708 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
 
using ll = long long;
#define int ll
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));
}
 
 
signed 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 41044 KB Output is correct
2 Correct 19 ms 41076 KB Output is correct
3 Correct 20 ms 41072 KB Output is correct
4 Correct 20 ms 41024 KB Output is correct
5 Correct 20 ms 41044 KB Output is correct
6 Correct 20 ms 41044 KB Output is correct
7 Correct 20 ms 41044 KB Output is correct
8 Correct 20 ms 41036 KB Output is correct
9 Correct 20 ms 41044 KB Output is correct
10 Correct 20 ms 41056 KB Output is correct
11 Correct 26 ms 41044 KB Output is correct
12 Correct 67 ms 41072 KB Output is correct
13 Correct 24 ms 41172 KB Output is correct
14 Correct 25 ms 41100 KB Output is correct
15 Correct 25 ms 41140 KB Output is correct
16 Correct 24 ms 41160 KB Output is correct
17 Correct 26 ms 41156 KB Output is correct
18 Correct 25 ms 41172 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 41044 KB Output is correct
2 Correct 19 ms 41076 KB Output is correct
3 Correct 20 ms 41072 KB Output is correct
4 Correct 20 ms 41024 KB Output is correct
5 Correct 20 ms 41044 KB Output is correct
6 Correct 20 ms 41044 KB Output is correct
7 Correct 20 ms 41044 KB Output is correct
8 Correct 20 ms 41036 KB Output is correct
9 Correct 20 ms 41044 KB Output is correct
10 Correct 20 ms 41056 KB Output is correct
11 Correct 26 ms 41044 KB Output is correct
12 Correct 67 ms 41072 KB Output is correct
13 Correct 24 ms 41172 KB Output is correct
14 Correct 25 ms 41100 KB Output is correct
15 Correct 25 ms 41140 KB Output is correct
16 Correct 24 ms 41160 KB Output is correct
17 Correct 26 ms 41156 KB Output is correct
18 Correct 25 ms 41172 KB Output is correct
19 Incorrect 117 ms 42640 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 47 ms 41036 KB Output is correct
2 Correct 24 ms 41004 KB Output is correct
3 Correct 25 ms 41008 KB Output is correct
4 Correct 41 ms 41132 KB Output is correct
5 Correct 80 ms 41412 KB Output is correct
6 Correct 21 ms 41068 KB Output is correct
7 Correct 24 ms 41556 KB Output is correct
8 Correct 23 ms 41492 KB Output is correct
9 Correct 26 ms 41568 KB Output is correct
10 Correct 42 ms 41588 KB Output is correct
11 Correct 109 ms 41948 KB Output is correct
12 Correct 34 ms 45776 KB Output is correct
13 Correct 33 ms 45780 KB Output is correct
14 Correct 35 ms 45824 KB Output is correct
15 Correct 61 ms 45892 KB Output is correct
16 Correct 172 ms 46324 KB Output is correct
17 Correct 250 ms 136560 KB Output is correct
18 Correct 246 ms 136500 KB Output is correct
19 Correct 258 ms 136500 KB Output is correct
20 Correct 305 ms 136756 KB Output is correct
21 Correct 624 ms 137296 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 43092 KB Output is correct
2 Correct 51 ms 43120 KB Output is correct
3 Incorrect 206 ms 43428 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 3322 ms 297308 KB Output is correct
2 Correct 3410 ms 303796 KB Output is correct
3 Correct 3390 ms 301916 KB Output is correct
4 Correct 3374 ms 303972 KB Output is correct
5 Correct 3333 ms 290988 KB Output is correct
6 Correct 3014 ms 235680 KB Output is correct
7 Correct 4454 ms 358948 KB Output is correct
8 Correct 4407 ms 358888 KB Output is correct
9 Correct 4357 ms 363348 KB Output is correct
10 Correct 4378 ms 361876 KB Output is correct
11 Correct 4332 ms 347120 KB Output is correct
12 Correct 3916 ms 269596 KB Output is correct
13 Correct 4366 ms 391508 KB Output is correct
14 Correct 4500 ms 391700 KB Output is correct
15 Correct 4224 ms 391700 KB Output is correct
16 Correct 4272 ms 390068 KB Output is correct
17 Correct 4177 ms 371960 KB Output is correct
18 Correct 3621 ms 279320 KB Output is correct
19 Correct 4383 ms 391652 KB Output is correct
20 Correct 4345 ms 391708 KB Output is correct
21 Correct 4350 ms 391612 KB Output is correct
22 Correct 4432 ms 390260 KB Output is correct
23 Correct 4175 ms 371980 KB Output is correct
24 Correct 3663 ms 279252 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 41044 KB Output is correct
2 Correct 19 ms 41076 KB Output is correct
3 Correct 20 ms 41072 KB Output is correct
4 Correct 20 ms 41024 KB Output is correct
5 Correct 20 ms 41044 KB Output is correct
6 Correct 20 ms 41044 KB Output is correct
7 Correct 20 ms 41044 KB Output is correct
8 Correct 20 ms 41036 KB Output is correct
9 Correct 20 ms 41044 KB Output is correct
10 Correct 20 ms 41056 KB Output is correct
11 Correct 26 ms 41044 KB Output is correct
12 Correct 67 ms 41072 KB Output is correct
13 Correct 24 ms 41172 KB Output is correct
14 Correct 25 ms 41100 KB Output is correct
15 Correct 25 ms 41140 KB Output is correct
16 Correct 24 ms 41160 KB Output is correct
17 Correct 26 ms 41156 KB Output is correct
18 Correct 25 ms 41172 KB Output is correct
19 Incorrect 117 ms 42640 KB Output isn't correct
20 Halted 0 ms 0 KB -