QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#278172 | #7883. Takeout Delivering | Vegetable_Dog# | TL | 1732ms | 98876kb | C++14 | 1.9kb | 2023-12-07 13:23:02 | 2023-12-07 13:23:02 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 600005;
#define mp make_pair
#define pb push_back
int n,m;
vector< int >G[N];
struct edge{
int u,v;
long long w;
bool operator <(const edge &o)const{
return w<o.w;
}
}e[2000005];
long long p[N];
int f[N];
int g[N][21];
int find(int x){
return (x==f[x]?x:f[x]=find(f[x]));
}
int dep[N];
void dfs(int u){
for(auto v:G[u]){
dep[v]=dep[u]+1;
dfs(v);
}
}
int LCA(int x,int y){
if(x==y)return x;
if(dep[x]<dep[y])swap(x,y);
for(int i=20;i>=0;i--)if(dep[g[x][i]]>=dep[y])x=g[x][i];
if(x==y)return x;
for(int i=20;i>=0;i--)if(g[x][i]!=g[y][i])x=g[x][i],y=g[y][i]; // fa[x][20]=fa[y][20]=0
return g[x][0];
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
long long w;
cin>>u>>v>>w;
e[i]=(edge){u,v,w};
}
sort(e+1, e+1+m);
for(int i=1;i<=n+n-1;i++){
f[i]=i;
}
int tot=n;
for(int i=1;i<=m;i++){
if(find(e[i].u)!=find(e[i].v)){
++tot;
g[find(e[i].u)][0]=tot;
G[tot].push_back(find(e[i].u));
G[tot].push_back(find(e[i].v));
// printf("%d -> %d\n",find(e[i].u), tot);
// printf("%d -> %d\n",find(e[i].v), tot);
g[find(e[i].v)][0]=tot;
f[find(e[i].u)]=tot;
f[find(e[i].v)]=tot;
p[tot]=e[i].w;
}
}
for(int j=1;j<=20;j++){
for(int i=1;i<=tot;i++){
g[i][j]=g[g[i][j-1]][j-1];
}
}
dep[tot]=1;
dfs(tot);
long long ans = 2000000005;
for(int i=1;i<=m;i++){
// printf("(%d, %d) w = %lld, LCA(1,%d)=%d, LCA(n,%d)=%d\n",e[i].u,e[i].v,e[i].w,e[i].u,LCA(1,e[i].u),e[i].v,LCA(n,e[i].v));
// printf(" 1: %lld, 2: %lld\n",max(p[LCA(1,e[i].v)], p[LCA(n,e[i].u)]) , max(p[LCA(1,e[i].u)], p[LCA(n,e[i].v)]));
long long t1 = max(p[LCA(1,e[i].v)], p[LCA(n,e[i].u)]);
long long t2 = max(p[LCA(1,e[i].u)], p[LCA(n,e[i].v)]);
if(e[i].w>=min(t1,t2))
ans = min(ans,e[i].w+ min( t1,t2 ));
// printf("ans = %lld\n",ans);
}
cout<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 17500kb
input:
4 6 1 2 2 1 3 4 1 4 7 2 3 1 2 4 3 3 4 9
output:
5
result:
ok 1 number(s): "5"
Test #2:
score: 0
Accepted
time: 566ms
memory: 87824kb
input:
300000 299999 80516 80517 597830404 110190 110191 82173886 218008 218009 954561262 250110 250111 942489774 66540 66541 156425292 34947 34948 239499776 273789 273790 453201232 84428 84429 439418398 98599 98600 326095035 55636 55637 355015760 158611 158612 684292473 43331 43332 43265001 171621 171622 ...
output:
1999991697
result:
ok 1 number(s): "1999991697"
Test #3:
score: 0
Accepted
time: 623ms
memory: 88028kb
input:
300000 299999 207226 231742 414945003 84591 210444 175968953 46327 51582 612565723 18773 141119 82562646 76139 286963 762958587 131867 224820 928900783 215240 216181 405340417 144725 290878 195350550 267216 268752 846015171 31413 255927 389339642 45219 147512 489502910 113391 215402 555706684 53359 ...
output:
1989898633
result:
ok 1 number(s): "1989898633"
Test #4:
score: 0
Accepted
time: 437ms
memory: 96148kb
input:
300000 299999 1 118488 989720257 1 181002 810258689 1 254222 172925351 1 176703 737330574 1 218306 941887568 1 105741 645573853 1 188490 794789787 1 273997 91455946 1 214929 293300204 1 127289 600097406 1 30589 330284120 1 128954 532459734 1 163729 627033607 1 24073 718818252 1 41571 755054850 1 560...
output:
725564985
result:
ok 1 number(s): "725564985"
Test #5:
score: 0
Accepted
time: 586ms
memory: 92064kb
input:
300000 299999 19784 19785 438457172 153297 239456 192671538 153297 202254 645947104 9640 9641 583410541 153297 221084 490232940 32210 32211 838809517 153297 171896 625627853 153297 216946 683286844 110843 110844 690710575 153297 176413 983037656 74908 74909 375017711 67676 67677 695121437 153297 196...
output:
1999992880
result:
ok 1 number(s): "1999992880"
Test #6:
score: 0
Accepted
time: 634ms
memory: 87816kb
input:
300000 299999 130662 244000 579178004 167657 294630 753914681 61924 61925 165841675 113560 113561 979316325 151574 218075 973289843 1224 1225 230803236 133441 133442 806726301 167309 249456 853031541 120245 120246 688705252 142688 217826 692299631 106114 106115 735998084 123268 123269 749737073 1208...
output:
1999989691
result:
ok 1 number(s): "1999989691"
Test #7:
score: 0
Accepted
time: 649ms
memory: 88564kb
input:
300000 299999 54474 108948 971770803 11077 22155 470962125 115359 230718 373029049 124472 248944 865510218 11958 23917 100575860 130349 260698 582886291 17563 35127 697131917 54427 108854 274252758 51546 103092 198620066 100126 200252 154524070 14994 29988 528701437 147502 295004 531813162 42285 845...
output:
1823402145
result:
ok 1 number(s): "1823402145"
Test #8:
score: 0
Accepted
time: 614ms
memory: 87772kb
input:
300000 299999 240182 240189 427579190 41871 41880 360542232 57131 57140 353813367 122650 122653 621913649 67332 67340 271427538 107523 107524 774306311 60374 60379 315636931 130805 130808 667109508 154531 154534 327293148 138561 138569 833879694 32543 32551 382610722 287398 287400 211744079 59693 59...
output:
1999983202
result:
ok 1 number(s): "1999983202"
Test #9:
score: 0
Accepted
time: 0ms
memory: 17696kb
input:
10 20 1 6 98 3 4 3 4 5 26 7 8 72 1 2 86 3 7 83 7 10 89 4 7 100 3 6 59 6 9 74 5 6 28 6 7 1 2 9 100 2 6 99 5 10 85 8 10 97 2 10 98 8 9 3 2 3 94 9 10 71
output:
170
result:
ok 1 number(s): "170"
Test #10:
score: 0
Accepted
time: 0ms
memory: 17476kb
input:
10 20 2 8 94 3 7 81 8 10 85 2 4 88 4 5 90 1 4 96 3 6 95 7 10 77 1 8 98 4 7 91 2 6 38 1 10 89 1 3 45 4 9 94 3 9 64 6 10 83 5 8 19 2 5 81 6 7 92 3 4 92
output:
89
result:
ok 1 number(s): "89"
Test #11:
score: 0
Accepted
time: 0ms
memory: 17492kb
input:
10 20 1 6 58 1 4 80 1 10 28 1 3 46 6 7 76 7 10 75 4 9 95 2 10 92 1 7 15 9 10 52 3 6 93 5 7 94 1 2 75 1 5 41 3 7 79 4 8 94 2 6 80 6 9 63 1 9 42 1 8 9
output:
28
result:
ok 1 number(s): "28"
Test #12:
score: 0
Accepted
time: 0ms
memory: 17520kb
input:
10 20 6 9 79 5 6 72 2 5 74 2 4 74 8 10 90 1 5 82 3 4 55 6 10 94 7 8 55 3 7 92 1 8 83 9 10 93 4 7 98 4 5 24 2 3 28 6 7 24 1 2 63 3 10 99 8 9 2 5 10 95
output:
158
result:
ok 1 number(s): "158"
Test #13:
score: 0
Accepted
time: 0ms
memory: 17520kb
input:
10 20 3 4 75 5 7 98 3 10 91 5 8 41 2 7 84 2 3 73 4 10 100 2 4 80 1 5 99 3 9 79 4 5 97 4 9 10 4 7 52 1 10 96 8 10 98 6 9 99 1 2 50 5 9 98 2 9 93 3 6 92
output:
96
result:
ok 1 number(s): "96"
Test #14:
score: 0
Accepted
time: 3ms
memory: 17696kb
input:
10 20 1 5 84 9 10 98 2 3 56 2 4 5 3 9 95 4 9 94 3 7 82 6 8 68 1 3 10 4 8 64 3 6 46 5 10 58 5 7 92 6 7 96 1 2 38 2 5 74 1 8 70 8 9 100 4 7 93 7 9 98
output:
132
result:
ok 1 number(s): "132"
Test #15:
score: 0
Accepted
time: 0ms
memory: 17640kb
input:
10 20 2 10 100 8 10 100 7 10 85 3 7 73 5 7 100 4 9 100 1 8 7 2 4 26 6 8 27 3 4 100 6 7 100 2 3 99 3 9 66 9 10 13 4 8 75 1 2 8 4 10 100 1 6 19 7 9 99 2 5 49
output:
107
result:
ok 1 number(s): "107"
Test #16:
score: 0
Accepted
time: 3ms
memory: 17536kb
input:
100 200 60 77 957 70 71 589 63 64 915 13 79 1000 8 9 757 41 42 141 21 53 1000 82 99 911 58 59 683 62 63 889 92 93 455 71 72 457 11 92 1000 9 43 1000 94 95 582 57 58 606 54 55 162 27 28 732 99 100 256 42 43 201 13 99 1000 15 73 1000 19 20 646 22 91 1000 22 50 1000 93 94 888 14 15 904 10 47 1000 68 83...
output:
1671
result:
ok 1 number(s): "1671"
Test #17:
score: 0
Accepted
time: 0ms
memory: 17544kb
input:
100 200 21 59 969 4 22 998 47 98 637 8 51 982 48 55 995 14 65 22 3 35 987 40 46 969 6 82 432 13 98 960 24 49 965 5 32 571 20 71 617 71 82 982 30 66 979 76 79 255 7 56 965 18 21 971 53 65 81 63 64 991 6 88 949 1 13 995 31 38 405 40 91 952 47 89 956 8 84 475 29 90 202 6 12 975 30 89 509 47 88 82 4 58 ...
output:
1859
result:
ok 1 number(s): "1859"
Test #18:
score: 0
Accepted
time: 0ms
memory: 17548kb
input:
100 200 19 29 909 22 86 785 1 56 28 38 85 942 1 52 89 1 78 693 4 30 975 54 99 939 1 89 461 1 59 390 1 95 576 1 92 343 1 11 876 1 85 109 29 78 958 74 81 981 10 49 799 1 39 767 41 92 641 1 69 149 1 34 984 13 70 896 32 44 949 1 20 137 1 90 85 2 70 545 4 58 910 33 60 818 89 96 906 66 100 997 1 55 85 1 9...
output:
896
result:
ok 1 number(s): "896"
Test #19:
score: 0
Accepted
time: 0ms
memory: 17544kb
input:
100 200 11 89 997 30 81 985 58 62 260 23 29 995 58 97 909 69 91 986 58 83 597 11 12 858 58 98 213 58 93 465 8 9 638 5 79 996 58 91 659 37 98 990 47 50 993 43 61 986 37 81 997 58 75 102 22 64 998 4 23 990 41 87 1000 73 95 982 30 31 722 13 43 998 17 18 659 42 52 974 32 48 939 53 90 996 69 86 943 4 5 2...
output:
1943
result:
ok 1 number(s): "1943"
Test #20:
score: 0
Accepted
time: 3ms
memory: 17556kb
input:
100 200 14 21 980 1 2 23 61 80 984 51 52 626 1 71 828 31 32 797 60 61 436 17 61 957 35 73 85 30 37 879 48 72 267 53 54 482 7 91 997 37 88 576 26 74 996 50 93 998 8 75 993 30 80 809 26 40 866 23 89 969 60 77 964 44 80 964 28 68 899 17 100 995 47 92 989 57 58 630 35 36 291 36 37 70 18 20 888 12 99 892...
output:
427
result:
ok 1 number(s): "427"
Test #21:
score: 0
Accepted
time: 0ms
memory: 17548kb
input:
100 200 11 12 980 33 66 341 60 88 997 41 83 156 11 22 995 29 75 736 44 73 996 8 68 965 49 62 935 65 81 998 5 10 229 58 74 934 55 88 998 27 90 999 10 21 409 3 74 911 11 84 1000 9 95 988 3 6 393 16 61 956 34 88 1000 34 67 966 21 43 66 12 61 837 14 56 413 12 42 998 26 52 778 6 12 830 63 78 844 6 36 893...
output:
1505
result:
ok 1 number(s): "1505"
Test #22:
score: 0
Accepted
time: 7ms
memory: 17592kb
input:
100 200 83 88 101 56 59 191 64 71 419 7 26 927 48 57 69 9 41 741 43 67 993 21 56 916 20 22 801 35 42 973 78 85 138 26 50 924 87 96 727 19 96 997 9 26 848 21 28 820 39 49 537 47 72 900 55 63 672 18 19 109 9 60 923 8 82 988 8 18 795 9 34 618 23 28 649 67 68 366 10 12 500 23 38 819 10 17 815 69 99 998 ...
output:
1402
result:
ok 1 number(s): "1402"
Test #23:
score: 0
Accepted
time: 1732ms
memory: 98876kb
input:
300000 1000000 279851 289752 999954614 161068 161069 686040658 98775 290773 999996999 152639 152640 726594968 83070 83071 812508473 91034 126281 999954538 86789 222983 999990457 95587 176851 999991161 33638 137265 999988809 84658 192641 999991026 153523 295952 999998616 174583 243251 999987129 12518...
output:
1998201565
result:
ok 1 number(s): "1998201565"
Test #24:
score: 0
Accepted
time: 1620ms
memory: 98724kb
input:
300000 1000000 156094 177846 999756574 62670 67365 998445252 208162 262938 951223122 4473 299766 999848707 55716 259406 991999708 200961 289293 999630537 226488 296872 999957282 60230 184345 693085189 63378 232935 999103539 170802 291169 998305128 138174 147828 999661605 7372 30652 999808376 19294 1...
output:
1984419418
result:
ok 1 number(s): "1984419418"
Test #25:
score: -100
Time Limit Exceeded
input:
300000 1000000 1 147883 857171646 218469 281753 668868929 87069 88444 765722112 80658 226298 847902531 52585 138505 745740009 55501 299252 995334032 22818 250405 984578623 143157 208305 995152517 5904 95707 811106518 86088 239508 980889473 11951 88291 984206415 90833 181809 922003327 1 92676 4902585...