QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#278172#7883. Takeout DeliveringVegetable_Dog#TL 1732ms98876kbC++141.9kb2023-12-07 13:23:022023-12-07 13:23:02

Judging History

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

  • [2023-12-07 13:23:02]
  • 评测
  • 测评结果:TL
  • 用时:1732ms
  • 内存:98876kb
  • [2023-12-07 13:23:02]
  • 提交

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

output:


result: