QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#67474#4126. 直径alpha1022100 ✓85ms10960kbC++231.1kb2022-12-10 16:19:032022-12-10 16:19:05

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-10 16:19:05]
  • 评测
  • 测评结果:100
  • 用时:85ms
  • 内存:10960kb
  • [2022-12-10 16:19:03]
  • 提交

answer

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 2e5;
int n;
int to[(N << 1) + 5],val[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
inline void add(int u,int v,int w)
{
	static int tot = 0;
	to[tot] = v,val[tot] = w,pre[tot] = first[u],first[u] = tot++;
}
int fa[N + 5],las[N + 5];
long long dis[N + 5];
int q[N + 5],head,tail;
int bfs(int s)
{
	head = tail = 0,fa[q[++tail] = s] = dis[s] = 0;
	for(register int p;head < tail;)
	{
		p = q[++head];
		for(register int i = first[p];~i;i = pre[i])
			if(to[i] ^ fa[p])
				fa[to[i]] = p,las[to[i]] = i,dis[to[i]] = dis[p] + val[i],q[++tail] = to[i];
	}
	int ret = 0;
	for(register int i = 1;i <= n;++i)
		if(dis[i] > dis[ret])
			ret = i;
	return ret;
}
int s,p;
long long ans;
int main()
{
	memset(first,-1,sizeof first);
	scanf("%d",&n);
	int u,v,w;
	for(register int i = 2;i <= n;++i)
		scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
	ans = dis[p = bfs(s = bfs(1))];
	for(;p ^ s;p = fa[p])
		--val[las[p]],--val[las[p] ^ 1];
	printf("%lld\n%d\n",ans,ans - dis[bfs(bfs(1))]);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 78ms
memory: 10956kb

input:

200000
128109 6076 1
24680 146413 1
95743 9145 951080
48860 198920 1
122018 68066 803924
99439 119189 1
196205 74025 1
45776 194688 6759
90085 30804 1
97116 106922 799
158894 141957 7501
187007 98504 12098
66124 51261 4337
64200 38741 359893
81862 93990 11260
89984 13818 1
12115 125784 1
93037 13510...

output:

30969406643
51543

result:

points 1.0 First Answer Correct, Second Answer Correct

Test #2:

score: 10
Accepted
time: 1ms
memory: 3680kb

input:

1000
684 154 28
3 772 333168
655 373 49
986 634 1
596 194 774375
909 158 1
50 745 1
409 282 1
958 709 1
807 936 1
863 550 32
468 634 1
277 250 1
351 987 1018511
483 90 1
107 295 550486
148 789 1
835 109 43
486 861 1
642 977 1
123 96 136466
561 218 1080008
219 1 1
162 4 1
288 709 1
680 728 1
249 278 ...

output:

166532681
264

result:

points 1.0 First Answer Correct, Second Answer Correct

Test #3:

score: 10
Accepted
time: 26ms
memory: 7100kb

input:

100000
54953 69220 675
30887 80247 1
99597 27698 7216
10118 27397 5360
61628 50700 483684
85360 76391 1
45080 53749 1
67023 87288 24
96430 383 1
95825 79255 1
26809 91097 1
83995 3340 1
72144 88253 146
50576 27302 1
2658 13725 1
85158 19637 411317
61903 67259 1
22565 425 1
84434 82087 105001
61751 6...

output:

15901281927
26527

result:

points 1.0 First Answer Correct, Second Answer Correct

Test #4:

score: 10
Accepted
time: 82ms
memory: 10884kb

input:

200000
74950 65730 10845
74080 60100 1
147182 58651 1504
149083 3432 715860
112882 114512 1
122652 86286 1364
118350 27439 1
148615 95012 1
180241 107653 510601
91045 51003 1
152240 136890 801331
93090 83916 1
101930 162140 1281
123329 158445 15860
62441 113562 591688
99731 156645 1
154226 140636 44...

output:

29063465409
48465

result:

points 1.0 First Answer Correct, Second Answer Correct

Test #5:

score: 10
Accepted
time: 1ms
memory: 4272kb

input:

100
76 23 1
51 34 1
80 26 1
19 67 318498
56 7 2
58 38 2
23 97 1
41 77 1
91 59 144845
17 24 2
29 44 503703
71 55 1
12 30 1
6 45 1
22 60 1
66 45 1
31 18 8
37 10 1
49 84 130821
2 18 1
37 46 3
71 24 1
20 22 1
24 93 1
28 33 1
8 3 1
47 69 268722
63 78 6
70 34 1
25 41 501654
30 90 1
50 85 1
85 20 1
95 60 3...

output:

13936888
26

result:

points 1.0 First Answer Correct, Second Answer Correct

Test #6:

score: 10
Accepted
time: 32ms
memory: 7844kb

input:

100000
1025 71891 1
91324 91771 1
82515 61751 882128
96538 93015 684
24223 98850 1
15585 43743 1
74482 46925 1
37139 43380 624
28608 84490 615373
71652 50960 1
15366 48213 584718
43189 49538 1
26971 47831 475727
1665 47480 1
71908 80123 1504
13318 87617 140
13324 59308 489272
19535 88300 1
91225 368...

output:

15913277381
26517

result:

points 1.0 First Answer Correct, Second Answer Correct

Test #7:

score: 10
Accepted
time: 2ms
memory: 3688kb

input:

1000
464 31 82
84 639 1
498 795 1081883
235 915 569579
43 786 144465
989 879 360317
244 203 34
8 688 144860
939 138 1
209 100 1
700 124 622792
90 339 1
751 329 19
915 573 612375
680 537 1
313 597 1
821 419 72
457 764 1
320 811 55
307 12 359803
662 189 1
788 205 1
126 484 1
609 131 782112
512 106 1
2...

output:

149116180
245

result:

points 1.0 First Answer Correct, Second Answer Correct

Test #8:

score: 10
Accepted
time: 85ms
memory: 10960kb

input:

200000
140067 12460 1
74823 5630 121049
78181 110643 1
69994 161853 1
61906 35864 14093
157475 165355 6016
591 188499 11573
40815 145572 1
124291 33261 551334
41896 158858 1
109248 77594 5324
82416 130097 8087
128228 83754 1
193378 133515 667214
143572 157000 6963
113433 132622 1
26825 154410 1
8086...

output:

30838958575
51530

result:

points 1.0 First Answer Correct, Second Answer Correct

Test #9:

score: 10
Accepted
time: 1ms
memory: 3580kb

input:

100
64 35 1
71 66 6
57 41 1
23 6 1
25 61 777570
84 30 1
49 81 1
48 43 7
82 98 1
24 48 1
76 26 690684
64 42 1
99 7 1
65 86 319814
48 66 1
6 4 1
31 39 1
99 14 1
8 44 432101
45 9 897592
69 53 1
21 33 1
1 49 1
91 31 9
54 55 2
95 49 1
69 7 1
50 78 926458
65 27 471295
96 19 1
70 95 1
40 16 1
24 90 1
15 93...

output:

16929786
27

result:

points 1.0 First Answer Correct, Second Answer Correct

Test #10:

score: 10
Accepted
time: 33ms
memory: 7068kb

input:

100000
16919 89014 320
92806 79604 4062
45436 65412 535531
60253 81159 81
11711 160 928476
20110 40238 183299
67607 30477 1
88895 33346 391267
59963 42950 683983
8082 98780 1
90226 34383 231835
51544 86471 1
12288 5466 1
61077 6735 1
27387 23829 1818
98555 20827 9009
66051 20795 1
68082 98453 1
3663...

output:

14091823360
23482

result:

points 1.0 First Answer Correct, Second Answer Correct