Submission #210854

#	Time	Username	Problem	Language	Result	Execution time	Memory
210854		Lawliet	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	693 ms	32044 KiB

diameter

#include <bits/stdc++.h>
 
using namespace std;
typedef long long int lli;
typedef pair<int,int> pii;
 
const int MAXN = 100010;
 
class SegmentTree
{
	public:
 
		int getLeft(int node) { return 2*node; }
		int getRight(int node) { return 2*node + 1; }
 
		void refresh(int node, int l, int r)
		{
			if( lazy[node] == 0 ) return;
 
			lli lz = lazy[node];
			lazy[node] = 0;
 
			mx[node] += lz;
 
			if( l == r ) return;
 
			lazy[ getLeft(node) ] += lz;
			lazy[ getRight(node) ] += lz;
		}
 
		void update(int node, int l, int r, int i, int j, lli v)
		{
			refresh( node , l , r );
 
			if( j < l || r < i ) return;
			if( i <= l && r <= j )
			{
				lazy[node] += v;
				refresh( node , l , r );
 
				return;
			} 
 
			int m = ( l + r )/2;
 
			update( getLeft(node) , l , m , i , j , v );
			update( getRight(node) , m + 1 , r , i , j , v );
 
			mx[node] = max( mx[ getLeft(node) ] , mx[ getRight(node) ] );
		}
 
		lli query(int node, int l, int r, int i, int j)
		{
			refresh( node , l , r );
 
			if( j < l || r < i ) return 0;
			if( i <= l && r <= j ) return mx[node];
 
			int m = ( l + r )/2;
 
			lli mxLeft = query( getLeft(node) , l , m , i , j );
			lli mxRight = query( getRight(node) , m + 1 , r , i , j );
 
			return max( mxLeft , mxRight );
		}
 
		SegmentTree()
		{
			memset( mx , 0 , sizeof(mx) );
			memset( lazy , 0 , sizeof(lazy) );
		}
 
	private:
 
		lli mx[4*MAXN];
		lli lazy[4*MAXN];
};
 
int n, q;
int curTime;
 
int tin[MAXN];
int tout[MAXN];
int node[MAXN];
int indSubtree[MAXN];
 
lli maxW;
lli lastAns;
 
lli value[MAXN];
lli weight[MAXN];
 
pii edge[MAXN];
 
vector< int > adj[MAXN];
vector< int > indEdge[MAXN];
 
multiset< lli > paths;
 
SegmentTree SEG;
 
void DFS(int cur, int p)
{
	tin[cur] = ++curTime;
	node[curTime] = cur;
 
	for(int i = 0 ; i < adj[cur].size() ; i++)
	{
		int viz = adj[cur][i];
 
		if( viz != p ) 
			DFS( viz , cur );
	}
 
	tout[cur] = curTime;
}
 
lli diameter()
{
	lli sum = 0;
	auto it = paths.end();
 
	it--;
	sum += *it;
 
	it--;
	sum += *it;
 
	return sum;
}
 
int main()
{
	scanf("%d %d %lld",&n,&q,&maxW);
 
	for(int i = 1 ; i < n ; i++)
	{
		int U, V;
		lli W;
		scanf("%d %d %lld",&U,&V,&W);
 
		adj[U].push_back( V );
		adj[V].push_back( U );
 
		indEdge[U].push_back( i );
		indEdge[V].push_back( i );
 
		weight[i] = W;
		edge[i] = { U , V };
	}
 
	DFS( 1 , 1 );
 
	for(int i = 1 ; i < n ; i++)
	{
		int U = edge[i].first;
		int V = edge[i].second;
 
		if( tin[U] > tin[V] ) swap( U , V );
 
		SEG.update( 1 , 1 , n , tin[V] , tout[V] , weight[i] );
	}
 
	paths.insert( 0 );
 
	for(int i = 0 ; i < adj[1].size() ; i++)
	{
		int viz = adj[1][i];
 
		value[i] = SEG.query( 1 , 1 , n , tin[viz] , tout[viz] );
 
		paths.insert( value[i] );
 
		for(int j = tin[viz] ; j <= tout[viz] ; j++)
			indSubtree[ node[j] ] = i;
	}
 
	for(int i = 1 ; i <= q ; i++)
	{
		lli d, e;
		scanf("%lld %lld",&d,&e);
 
		d = ( d + lastAns )%( n - 1 ) + 1;
		e = ( e + lastAns )%maxW;
 
		int U = edge[d].first;
		int V = edge[d].second;
 
		if( tin[U] > tin[V] ) swap( U , V );
 
		SEG.update( 1 , 1 , n , tin[V] , tout[V] , -weight[d] );
		weight[d] = e;
		SEG.update( 1 , 1 , n , tin[V] , tout[V] , weight[d] );
 
		int curInd = indSubtree[V];
 
		paths.erase( paths.find( value[curInd] ) );
		value[curInd] = SEG.query( 1 , 1 , n , tin[ adj[1][curInd] ] , tout[ adj[1][curInd] ] );
		paths.insert( value[curInd] );
 
		lastAns = diameter();
		printf("%lld\n",lastAns);
	}
}

Compilation message (stderr)

diameter.cpp: In function 'void DFS(int, int)':
diameter.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
diameter.cpp: In function 'int main()':
diameter.cpp:166:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[1].size() ; i++)
                  ~~^~~~~~~~~~~~~~~
diameter.cpp:134:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %lld",&n,&q,&maxW);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:140:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %lld",&U,&V,&W);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:181:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&d,&e);
   ~~~~~^~~~~~~~~~~~~~~~~~~

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