QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#67474 | #4126. 直径 | alpha1022 | 100 ✓ | 85ms | 10960kb | C++23 | 1.1kb | 2022-12-10 16:19:03 | 2022-12-10 16:19:05 |
Judging History
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