oj.uz

Submission #210854

# Submission time Handle Problem Language Result Execution time Memory
210854 2020-03-18T21:39:27 Z Lawliet Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 693 ms 32044 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 11384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 11384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 11256 KB Output is correct
2 Correct 19 ms 11288 KB Output is correct
3 Correct 17 ms 11384 KB Output is correct
4 Correct 39 ms 11512 KB Output is correct
5 Correct 126 ms 12476 KB Output is correct
6 Correct 18 ms 11300 KB Output is correct
7 Correct 18 ms 11416 KB Output is correct
8 Correct 15 ms 11388 KB Output is correct
9 Correct 20 ms 11468 KB Output is correct
10 Correct 41 ms 11552 KB Output is correct
11 Correct 168 ms 12452 KB Output is correct
12 Correct 21 ms 12152 KB Output is correct
13 Correct 24 ms 12124 KB Output is correct
14 Correct 23 ms 12152 KB Output is correct
15 Correct 54 ms 12408 KB Output is correct
16 Correct 204 ms 13416 KB Output is correct
17 Correct 186 ms 28140 KB Output is correct
18 Correct 169 ms 28108 KB Output is correct
19 Correct 236 ms 28128 KB Output is correct
20 Correct 310 ms 28276 KB Output is correct
21 Correct 693 ms 29464 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 11484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 22368 KB Output is correct
2 Correct 624 ms 26580 KB Output is correct
3 Correct 547 ms 26520 KB Output is correct
4 Correct 593 ms 26640 KB Output is correct
5 Correct 578 ms 27084 KB Output is correct
6 Correct 514 ms 29864 KB Output is correct
7 Correct 572 ms 28096 KB Output is correct
8 Correct 606 ms 28224 KB Output is correct
9 Correct 651 ms 28252 KB Output is correct
10 Correct 685 ms 28372 KB Output is correct
11 Correct 589 ms 28816 KB Output is correct
12 Correct 586 ms 30888 KB Output is correct
13 Correct 524 ms 31028 KB Output is correct
14 Correct 650 ms 31068 KB Output is correct
15 Correct 641 ms 31132 KB Output is correct
16 Correct 612 ms 31044 KB Output is correct
17 Correct 655 ms 31324 KB Output is correct
18 Correct 607 ms 31988 KB Output is correct
19 Correct 480 ms 30956 KB Output is correct
20 Correct 554 ms 30892 KB Output is correct
21 Correct 617 ms 31080 KB Output is correct
22 Correct 605 ms 31264 KB Output is correct
23 Correct 634 ms 31324 KB Output is correct
24 Correct 592 ms 32044 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 11384 KB Output isn't correct
2 Halted 0 ms 0 KB -