Submission #210850

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
210850	2020-03-18T21:37:04 Z	Lawliet	Dynamic Diameter (CEOI19_diameter)	C++17	24 / 100	5000 ms	12536 KB

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

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	4988 KB	Output is correct
2	Correct	12 ms	5112 KB	Output is correct
3	Correct	10 ms	4984 KB	Output is correct
4	Correct	10 ms	4984 KB	Output is correct
5	Correct	9 ms	4984 KB	Output is correct
6	Correct	11 ms	4984 KB	Output is correct
7	Correct	11 ms	4984 KB	Output is correct
8	Correct	13 ms	4984 KB	Output is correct
9	Correct	12 ms	4984 KB	Output is correct
10	Correct	12 ms	4984 KB	Output is correct
11	Correct	11 ms	4984 KB	Output is correct
12	Correct	11 ms	5112 KB	Output is correct
13	Correct	11 ms	5112 KB	Output is correct
14	Correct	10 ms	5112 KB	Output is correct
15	Correct	10 ms	5112 KB	Output is correct
16	Correct	11 ms	4984 KB	Output is correct
17	Correct	10 ms	4984 KB	Output is correct
18	Correct	11 ms	5112 KB	Output is correct

Subtask #2
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	4988 KB	Output is correct
2	Correct	12 ms	5112 KB	Output is correct
3	Correct	10 ms	4984 KB	Output is correct
4	Correct	10 ms	4984 KB	Output is correct
5	Correct	9 ms	4984 KB	Output is correct
6	Correct	11 ms	4984 KB	Output is correct
7	Correct	11 ms	4984 KB	Output is correct
8	Correct	13 ms	4984 KB	Output is correct
9	Correct	12 ms	4984 KB	Output is correct
10	Correct	12 ms	4984 KB	Output is correct
11	Correct	11 ms	4984 KB	Output is correct
12	Correct	11 ms	5112 KB	Output is correct
13	Correct	11 ms	5112 KB	Output is correct
14	Correct	10 ms	5112 KB	Output is correct
15	Correct	10 ms	5112 KB	Output is correct
16	Correct	11 ms	4984 KB	Output is correct
17	Correct	10 ms	4984 KB	Output is correct
18	Correct	11 ms	5112 KB	Output is correct
19	Correct	236 ms	5380 KB	Output is correct
20	Correct	244 ms	5372 KB	Output is correct
21	Correct	262 ms	5372 KB	Output is correct
22	Correct	320 ms	5380 KB	Output is correct
23	Correct	1916 ms	5880 KB	Output is correct
24	Correct	2114 ms	5708 KB	Output is correct
25	Correct	2232 ms	5884 KB	Output is correct
26	Correct	2742 ms	6072 KB	Output is correct

Subtask #3
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	4984 KB	Output is correct
2	Correct	15 ms	5012 KB	Output is correct
3	Correct	20 ms	5112 KB	Output is correct
4	Correct	42 ms	5244 KB	Output is correct
5	Correct	127 ms	6216 KB	Output is correct
6	Correct	12 ms	4984 KB	Output is correct
7	Correct	13 ms	5088 KB	Output is correct
8	Correct	15 ms	5000 KB	Output is correct
9	Correct	40 ms	5164 KB	Output is correct
10	Correct	275 ms	5396 KB	Output is correct
11	Correct	1315 ms	6392 KB	Output is correct
12	Correct	20 ms	5524 KB	Output is correct
13	Correct	46 ms	5496 KB	Output is correct
14	Correct	283 ms	5652 KB	Output is correct
15	Correct	2602 ms	5924 KB	Output is correct
16	Execution timed out	5009 ms	6300 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #4
0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	5112 KB	Output is correct
2	Correct	309 ms	5280 KB	Output is correct
3	Correct	1513 ms	6132 KB	Output is correct
4	Correct	3016 ms	6608 KB	Output is correct
5	Correct	318 ms	6040 KB	Output is correct
6	Correct	3118 ms	6236 KB	Output is correct
7	Execution timed out	5025 ms	6552 KB	Time limit exceeded
8	Halted	0 ms	0 KB	-

Subtask #5
0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	5015 ms	12536 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	4988 KB	Output is correct
2	Correct	12 ms	5112 KB	Output is correct
3	Correct	10 ms	4984 KB	Output is correct
4	Correct	10 ms	4984 KB	Output is correct
5	Correct	9 ms	4984 KB	Output is correct
6	Correct	11 ms	4984 KB	Output is correct
7	Correct	11 ms	4984 KB	Output is correct
8	Correct	13 ms	4984 KB	Output is correct
9	Correct	12 ms	4984 KB	Output is correct
10	Correct	12 ms	4984 KB	Output is correct
11	Correct	11 ms	4984 KB	Output is correct
12	Correct	11 ms	5112 KB	Output is correct
13	Correct	11 ms	5112 KB	Output is correct
14	Correct	10 ms	5112 KB	Output is correct
15	Correct	10 ms	5112 KB	Output is correct
16	Correct	11 ms	4984 KB	Output is correct
17	Correct	10 ms	4984 KB	Output is correct
18	Correct	11 ms	5112 KB	Output is correct
19	Correct	236 ms	5380 KB	Output is correct
20	Correct	244 ms	5372 KB	Output is correct
21	Correct	262 ms	5372 KB	Output is correct
22	Correct	320 ms	5380 KB	Output is correct
23	Correct	1916 ms	5880 KB	Output is correct
24	Correct	2114 ms	5708 KB	Output is correct
25	Correct	2232 ms	5884 KB	Output is correct
26	Correct	2742 ms	6072 KB	Output is correct
27	Correct	18 ms	4984 KB	Output is correct
28	Correct	15 ms	5012 KB	Output is correct
29	Correct	20 ms	5112 KB	Output is correct
30	Correct	42 ms	5244 KB	Output is correct
31	Correct	127 ms	6216 KB	Output is correct
32	Correct	12 ms	4984 KB	Output is correct
33	Correct	13 ms	5088 KB	Output is correct
34	Correct	15 ms	5000 KB	Output is correct
35	Correct	40 ms	5164 KB	Output is correct
36	Correct	275 ms	5396 KB	Output is correct
37	Correct	1315 ms	6392 KB	Output is correct
38	Correct	20 ms	5524 KB	Output is correct
39	Correct	46 ms	5496 KB	Output is correct
40	Correct	283 ms	5652 KB	Output is correct
41	Correct	2602 ms	5924 KB	Output is correct
42	Execution timed out	5009 ms	6300 KB	Time limit exceeded
43	Halted	0 ms	0 KB	-

Submission #210850

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 13.0 / 13.0

Subtask #3 0 / 7.0

Subtask #4 0 / 18.0

Subtask #5 0 / 24.0

Subtask #6 0 / 27.0

Subtask #1
11.0 / 11.0

Subtask #2
13.0 / 13.0

Subtask #3
0 / 7.0

Subtask #4
0 / 18.0

Subtask #5
0 / 24.0

Subtask #6
0 / 27.0