Submission #199993

#	Time	Username	Problem	Language	Result	Execution time	Memory
199993		davitmarg	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	5104 ms	471424 KiB

diameter

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;
 
struct segtree
{
	vector<LL> d;
	vector<pair<LL,int>> t;
 
	void build(int v,int l,int r,vector<int> &a,vector<LL>& D,unordered_map<int,int>&b)
	{
		if(l==r)
		{
			t[v].first=D[a[l]];
			t[v].second=b[a[l]];
			d[v]=0;
			return;
		}
		int m=(l+r)/2;
		build(v*2,l,m,a,D,b);
		build(v*2+1,m+1,r,a,D,b);
		t[v]=max(t[v*2],t[v*2+1]);
	}
 
	segtree(int n=0)
	{
		t.resize(n*4+5);
		d.resize(n*4+5);
	}
 
	segtree(vector<int>& a,vector<LL>& D,unordered_map<int,int>& b)
	{
		t.resize(a.size()*4+5);
		d.resize(a.size()*4+5);
		build(1,0,a.size()-1,a,D,b);
	}
 
	void push(int v,int l,int r,int f=1)
	{
		if(d[v]==0)
			return;
		if(l!=r)
		{
			int m=(l+r)/2;
			d[v*2]+=d[v];
			d[v*2+1]+=d[v];
			if(f)
			{
				push(v*2,l,m,0);
				push(v*2+1,m+1,r,0);
			}
		}
		t[v].first+=d[v];
		d[v]=0;
	}
 
	pair<LL,int> get(int v,int l,int r,int i,int j)
	{
		push(v,l,r);
		if(i>j)
			return MP(0,0);
		if(l==i && r==j)
			return t[v];
		int m=(l+r)/2;
		return max(
			get(v*2,l,m,i,min(j,m)),
			get(v*2+1,m+1,r,max(i,m+1),j)
		);
	}
 
	void add(int v,int l,int r,int i,int j,LL val)
	{
		push(v,l,r);
		if(i>j)
			return;
		if(l==i && r==j)
		{
			d[v]+=val;
			push(v,l,r);
			return;
		}
		int m=(l+r)/2;
		add(v*2,l,m,i,min(j,m),val);
		add(v*2+1,m+1,r,max(i,m+1),j,val);
		t[v]=max(t[v*2],t[v*2+1]);
	}
	
};
 
LL n, q;
LL W, w[100005],sz[100005],used[100005],color[100005],col, ans;
vector<LL> d(100005);
vector<pair<int, int>> g[100005];
vector<int> ord[100005];
segtree seg[100005];
unordered_map<int,int> subtree[100005],tin[100005],tout[100005],pos[100005],centr[100005];
multiset<LL> best;
void dfsSize(int v,int p)
{
	color[v]=col;
	sz[v]=1;
	for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i].first;
		if(used[to] || to==p)
			continue;
		dfsSize(to,v);
		sz[v]+=sz[to];
	}
}
 
int centroid(int v)
{
	col++;
	dfsSize(v,0);
	col++;
	queue<int> q;
	q.push(v);
	while (!q.empty())
	{
		int x=q.front();
		q.pop();
		color[x]=col;
		bool is=(sz[v]>=(sz[v]-sz[x])*2);
		for(int i=0;i<g[x].size();i++)
		{
			int to=g[x][i].first;
			if(color[to]==col || used[to])
				continue;
			q.push(to);
			is&=(sz[v]>=sz[to]*2);
		}
 
		if(is)
			return x;
	}
}
 
void dfs(int Centr,int Sub,int v,int p,LL dist)
{
	d[v]=dist;
	subtree[Centr][v]=Sub;
	ord[Centr].PB(v);
	tin[Centr][v]=ord[Centr].size()-1;
 
	for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i].first;
		int d=g[v][i].second;
		if(to==p || used[to])
			continue;
		pos[Centr][d]=to;
		dfs(Centr,Sub,to,v,dist+w[d]);
	}
 
	tout[Centr][v]=ord[Centr].size()-1;
 
}
 
LL getMax(int v)
{
	pair<LL, LL> mx1,mx2;
	mx1 = seg[v].get(1, 0, ord[v].size() - 1, 0, ord[v].size() - 1);
	if(mx1.first==0)
		return 0;
	mx2 = max(
		seg[v].get(1, 0, ord[v].size() - 1, 0, tin[v][mx1.second] - 1),
		seg[v].get(1, 0, ord[v].size() - 1, tout[v][mx1.second] + 1, ord[v].size() - 1)
	);
	return mx1.first+mx2.first;
}
 
 
void calc(int v)
{
	used[v]=1;
	ord[v].PB(v);
	tin[v][v]=ord[v].size()-1;
	d[v]=0;
	for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i].first;
		int d=g[v][i].second;
		if(used[to])
			continue;
		pos[v][d]=to;
		dfs(v,to,to,v,w[d]);
	}
	tout[v][v]=ord[v].size()-1;
	seg[v]=segtree(ord[v],d,subtree[v]);
 
 
	LL mx=getMax(v);
	//cout<<"!!!"<<v<<" > "<<mx<<endl;
	best.insert(mx);
 
	for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i].first;
		if(used[to])
			continue;
		calc(centr[v][to]=centroid(to));
	}
}
 
void solve(int v,int P,LL val)
{
	if(pos[v].find(P)==pos[v].end())
		return;
	int p=pos[v][P];
 
 
	LL mx;
	mx=getMax(v);
	//cout<<"!!"<<v<<" > "<<mx<<endl;
	best.erase(best.find(mx));
	seg[v].add(1, 0, ord[v].size() - 1, tin[v][p], tout[v][p], val);
 
 
	mx=getMax(v);
	//cout<<"!"<<v<<" > "<<mx<<endl;
 
	best.insert(mx);
	solve(centr[v][subtree[v][p]],P,val);
} 
int main()
{
	cin >> n >> q >> W;
	for (int i = 1; i <= n - 1; i++)
	{
		int a, b;
		scanf("%d%d%lld", &a, &b, w + i);
		g[a].PB(MP(b, i));
		g[b].PB(MP(a, i));
	}
	calc(centr[0][1]=centroid(1));
	while (q--)
	{
		LL p;
		LL D;
		scanf("%lld%lld", &p, &D);
		p = (p + ans) % (n - 1);
		D = (D + ans) % W;
		p++;
		solve(centr[0][1],p,D-w[p]);
		w[p]=D;
 
		if(!best.empty())
		{
			auto it=best.end();
			--it;
			ans=(*it);
		}
		else
			ans=0;
 
		printf("%lld\n", ans);
	}
 
	return 0;
}
 
/*
 
7 1 1000 
1 2 10
2 3 1
2 4 1
1 5 1
5 6 1
5 7 1
0 1
 
 
*/

Compilation message (stderr)

diameter.cpp: In function 'void dfsSize(int, int)':
diameter.cpp:123:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
diameter.cpp: In function 'int centroid(int)':
diameter.cpp:146:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[x].size();i++)
               ~^~~~~~~~~~~~
diameter.cpp: In function 'void dfs(int, int, int, int, long long int)':
diameter.cpp:167:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
diameter.cpp: In function 'void calc(int)':
diameter.cpp:201:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
diameter.cpp:218:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
diameter.cpp: In function 'int centroid(int)':
diameter.cpp:158:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
diameter.cpp: In function 'int main()':
diameter.cpp:253:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld", &a, &b, w + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:262:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &p, &D);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27