Submission #210850

#	Time	Username	Problem	Language	Result	Execution time	Memory
210850		Lawliet	Dynamic Diameter (CEOI19_diameter)	C++17	24 / 100	5025 ms	12536 KiB

diameter

#include <bits/stdc++.h>
 
using namespace std;
typedef long long int lli;
 
const int MAXN = 100010;
 
int n, q;
 
int weight[MAXN];
 
lli maxW;
lli lastAns;
 
lli prof[MAXN];
 
vector< int > adj[MAXN];
vector< int > indEdge[MAXN];
 
void DFS(int cur, int p)
{
	for(int i = 0 ; i < adj[cur].size() ; i++)
	{
		int viz = adj[cur][i];
		int ind = indEdge[cur][i];
 
		if( viz == p ) continue;
 
		prof[viz] = prof[cur] + weight[ind];
 
		DFS( viz , cur );
	}
}
 
int getFarthest()
{
	int opt = 1;
 
	for(int i = 2 ; i <= n ; i++)
		if( prof[opt] < prof[i] ) opt = i;
 
	return opt;
}
 
lli diameter()
{
	prof[1] = 0; 
	DFS( 1 , 1 );
 
	int cur = getFarthest();
	prof[cur] = 0;
	DFS( cur , cur );
 
	return prof[ getFarthest() ];
}
 
int main()
{
	scanf("%d %d %lld",&n,&q,&maxW);
 
	for(int i = 1 ; i < n ; i++)
	{
		int U, V, W;
		scanf("%d %d %d",&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;
	}
 
	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;
 
		weight[d] = e;
 
		lastAns = diameter();
		printf("%lld\n",lastAns);
	}
}

Compilation message (stderr)

diameter.cpp: In function 'void DFS(int, int)':
diameter.cpp:22: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:59: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:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&U,&V,&W);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
diameter.cpp:78: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: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27