oj.uz

Submission #542936

# Submission time Handle Problem Language Result Execution time Memory
542936 2022-03-28T13:25:59 Z blue Dynamic Diameter (CEOI19_diameter) C++17
18 / 100
 5000 ms 277584 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'0LL;
 
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 21 ms 37464 KB Output is correct
2 Correct 22 ms 37484 KB Output is correct
3 Correct 22 ms 37516 KB Output is correct
4 Correct 22 ms 37520 KB Output is correct
5 Correct 22 ms 37524 KB Output is correct
6 Correct 21 ms 37460 KB Output is correct
7 Correct 22 ms 37460 KB Output is correct
8 Correct 22 ms 37540 KB Output is correct
9 Correct 33 ms 37524 KB Output is correct
10 Correct 21 ms 37540 KB Output is correct
11 Correct 21 ms 37460 KB Output is correct
12 Correct 18 ms 37520 KB Output is correct
13 Correct 29 ms 37580 KB Output is correct
14 Correct 18 ms 37516 KB Output is correct
15 Correct 19 ms 37544 KB Output is correct
16 Correct 18 ms 37560 KB Output is correct
17 Correct 19 ms 37644 KB Output is correct
18 Correct 18 ms 37588 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37464 KB Output is correct
2 Correct 22 ms 37484 KB Output is correct
3 Correct 22 ms 37516 KB Output is correct
4 Correct 22 ms 37520 KB Output is correct
5 Correct 22 ms 37524 KB Output is correct
6 Correct 21 ms 37460 KB Output is correct
7 Correct 22 ms 37460 KB Output is correct
8 Correct 22 ms 37540 KB Output is correct
9 Correct 33 ms 37524 KB Output is correct
10 Correct 21 ms 37540 KB Output is correct
11 Correct 21 ms 37460 KB Output is correct
12 Correct 18 ms 37520 KB Output is correct
13 Correct 29 ms 37580 KB Output is correct
14 Correct 18 ms 37516 KB Output is correct
15 Correct 19 ms 37544 KB Output is correct
16 Correct 18 ms 37560 KB Output is correct
17 Correct 19 ms 37644 KB Output is correct
18 Correct 18 ms 37588 KB Output is correct
19 Incorrect 39 ms 38876 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 37484 KB Output is correct
2 Correct 18 ms 37544 KB Output is correct
3 Correct 18 ms 37536 KB Output is correct
4 Correct 34 ms 37716 KB Output is correct
5 Correct 87 ms 38672 KB Output is correct
6 Correct 23 ms 37536 KB Output is correct
7 Correct 26 ms 37836 KB Output is correct
8 Correct 20 ms 37840 KB Output is correct
9 Correct 24 ms 37968 KB Output is correct
10 Correct 40 ms 38172 KB Output is correct
11 Correct 132 ms 39244 KB Output is correct
12 Correct 32 ms 41556 KB Output is correct
13 Correct 31 ms 41548 KB Output is correct
14 Correct 35 ms 41548 KB Output is correct
15 Correct 57 ms 41812 KB Output is correct
16 Correct 170 ms 43040 KB Output is correct
17 Correct 262 ms 118844 KB Output is correct
18 Correct 257 ms 118972 KB Output is correct
19 Correct 263 ms 119100 KB Output is correct
20 Correct 323 ms 119220 KB Output is correct
21 Correct 760 ms 120604 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 39032 KB Output is correct
2 Correct 52 ms 39216 KB Output is correct
3 Incorrect 216 ms 39840 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3547 ms 232860 KB Output is correct
2 Correct 3564 ms 237552 KB Output is correct
3 Correct 3348 ms 236168 KB Output is correct
4 Correct 3346 ms 237712 KB Output is correct
5 Correct 3802 ms 228536 KB Output is correct
6 Correct 3085 ms 188392 KB Output is correct
7 Correct 4690 ms 277584 KB Output is correct
8 Execution timed out 5077 ms 277304 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37464 KB Output is correct
2 Correct 22 ms 37484 KB Output is correct
3 Correct 22 ms 37516 KB Output is correct
4 Correct 22 ms 37520 KB Output is correct
5 Correct 22 ms 37524 KB Output is correct
6 Correct 21 ms 37460 KB Output is correct
7 Correct 22 ms 37460 KB Output is correct
8 Correct 22 ms 37540 KB Output is correct
9 Correct 33 ms 37524 KB Output is correct
10 Correct 21 ms 37540 KB Output is correct
11 Correct 21 ms 37460 KB Output is correct
12 Correct 18 ms 37520 KB Output is correct
13 Correct 29 ms 37580 KB Output is correct
14 Correct 18 ms 37516 KB Output is correct
15 Correct 19 ms 37544 KB Output is correct
16 Correct 18 ms 37560 KB Output is correct
17 Correct 19 ms 37644 KB Output is correct
18 Correct 18 ms 37588 KB Output is correct
19 Incorrect 39 ms 38876 KB Output isn't correct
20 Halted 0 ms 0 KB -