제출 #542937

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
542937		blue	Dynamic Diameter (CEOI19_diameter)	C++17	42 / 100	4500 ms	391708 KiB

diameter

#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 / 11
• Subtask 2: 0 / 13
• Subtask 3: 7 / 7
• Subtask 4: 0 / 18
• Subtask 5: 24 / 24
• Subtask 6: 0 / 27